Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint
Share this Page URL
Help

CHAPTER 13

CHAPTER 13

  1. A power distribution network would be difficult to represent as a hierarchical structure, since the power-generating stations and supply substations may be cross-connected in a number of ways, rather than there being predecessor and successor installations. A node in a tree structure may have only one 'parent' node, but an electricity substation may receive power via one or more routes. The installations may be represented by a graph's vertices, with the connecting cables as the edges of the graph. The linkage between installations might be uni- or bidirectional, with the edge weightings corresponding to the power transmission capacity of the network's various cables.

  2. See discussion in the text.

  3. Contents of the adjacency matrix:

        Vertex[0] = "Sleepytown";
        Vertex[1] = "Much Snoring";
        Vertex[2] = "Great Snoring";
        Vertex[3] = "Little Snoring";
        Vertex[4] = "Lesser Snoring";
        Vertex[5] = "Snoring on Sea";
        Vertex[6] = "Snoring on the Hill";
        Edge[0][1] = 50;  // Sleepytown to Much Snoring
        Edge[1][0] = 50;  // Much Snoring to Sleepytown
        Edge[1][2] = 150; // Much Snoring to Great Snoring
        Edge[2][1] = 150; // Great Snoring to Much Snoring
        Edge[3][1] = 80;  // Little Snoring to Much Snoring
        Edge[2][3] = 180; // Great Snoring to Little Snoring
        Edge[2][6] = 150; // Great Snoring to Snoring on the Hill
        Edge[2][5] = 200; // Great Snoring to Snoring by Sea
        Edge[5][2] = 200; // Snoring on Sea to Great Snoring
        Edge[6][4] = 50;  // Snoring on the Hill to Lesser Snoring
        Edge[4][2] = 180; // Lesser Snoring to Great Snoring

    Breadth-first using Queue
    From Sleepytown: queue holds 0
    Dequeue: Enqueue 1: Dequeue: Enqueue 2: Dequeue:
    Enqueue 3 5 6:  Dequeue all: Enqueue 4: Dequeue
    Traversal: 0 1 2 3 5 6 4:
    Sleepytown -  Much  - Great - Little - Snoring on Sea -  Snoring on the Hill - Lesser Snoring
    
    Depth-first using Stack
    From Sleepytown: stack holds 0
    Pop, push 1: pop: push 2: pop: push 3 5 6 : pop 6: push 4: pop 4: pop 5: pop 3
    Traversal: 0 1 2 6 4 5 3
    Sleepytown - Much -Great - Snoring on the Hill - Lesser -Snoring on Sea
    - Little Snoring
    
    					  

    1. If the flight from Great Snoring to Much Snoring is withdrawn, then row subscript 2 is affected. Edges[2][1] is changed from 150 to 0 as shown in bold in the following table:



    2. A return flight is introduced from Snoring on the Hill to Great Snoring, a distance of 150 miles. Since the starting point is Vertex[5] then Edges[5][2] is changed to 150.



  4. For explanations of terms, see Chapter 13 (Section 13.19). Application to the first exercise: It would help in planning routes for power lines and associated installations, depending upon terrain—flat, hilly, water crossing—and on costs of underground or overhead cabling.6.

    1. Use the example given in Chapter 13 (Section 13.17), and view the animated sequence in the Graphs presentation. Starting with A, note distances to node A neighbours. They are

      B (10) C (5). Mark A checked

      At C, get distances from A:

      E (14) F (8). C checked



      At B, distances from A:

      D (14) B checked

      Get distance via F: G - destination (16) F

      Distance via E: H (18) E

      Distance via D: H (21) – larger than via E, don't replace. D

      Distance via H: I(24) H

      Distance via I: G(29) – larger than via F, don't replace I

      All vertices are checked—shortest distances are shown. Path is A—C—F—G, and the shortest distance is 16.



    2. Use the same process for F to D with the result shown alongside. Path is F—C—A—B—D, and the shortest distance is 22

    1. Apply Kruskal's algorithm by creating an ordered list of edges and weightings:



      Construct the tree by adding edges, in the increasing order of weight (shown in bold lines in the following figure):



      Add to tree:

      F-G

      E-F

      A-C

      A-B

      C-E

      omit B-E as this would produce a cycle

      D-G

      All vertices are now connected.

    2. See example in Chapter 13 (Section 13.19). Apply Prim's algorithm by choosing a start point, and then its nearest neighbour.

      Start at C: Choose A, then B. Next nearest neighbour is E. Now F, G, D. Produces the same tree as Kruskal's algorithm.



  5. No solution given since this is a practical exercise.

  6. Major changes are required, including the following:

    An extra row and column must be added to the matrix, requiring redeclaration of the arrays Vertex as String[8], Edges as int[8][8] and Visited as boolean[8].

    Statements must be written so as to add values as follows (also Visited[7] = false):



    The traversal and search methods will need to be changed to take into account that the matrix now contains eight columns …

    for (int column = 0; column <  8 ; column++) {
               if (Edge[current][column] != 0 && !visited[column])
                   myStack.push(column);
             } 

    … as will the method that displays the matrix contents:

    for (int i = 0; i <  8 ; i++) {
               System.out.print(Vertex[i]);
                for (int j = 0; j <  8 ; j++)
                    System.out.print(Edge[i][j] + " ");
                System.out.println();
          } 


  

You are currently reading a PREVIEW of this book.

                                                                                                                    

Get instant access to over $1 million worth of books and videos.

  

Start a Free 10-Day Trial


  
  • Safari Books Online
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint