CMSC 420 Answers to Selected Questions in Written Asst 2

For answers to other questions, please consult the instructor or ta during office hours.
  1. Follow the algorithm discussed in class: gr9 in the lecture notes
    Suppose you start with node A: then the steps are as follows:
    Step 1: add (a b 4)
    Step 2: add (b c 3)
    Step 3: add (c f 2)
    Step 4: add (e f 3)
    Step 5: add (b d 4)
    
    
    The total distance is 16, with the edges listed above. At each step, the new node in the edge is also addes to the connected list and deleted from the unconnected list. With a different starting point, the steps appear in a different order, but the same edges will appear.

  2. The point here is to apply the algorithm from class, page gr10. The name is a bit confusing here, since we are still forming a spanning tree (or free tree), not necessarily a chain. The name comes because for our given node, we will have the same shortest elementary chain from that node to all others as we will in the main graph. Moreover, we will only have one chain from the start node to each node. So this is a set of chains. Starting with node a, the steps proceed as follows:
    Step 1: add (a b 4)
    Step 2: Shortest paths: a: (a c 10) b: (b c 3)
    	Costs from a:      10         7
    	Choose (b c 3)
    Step 3:  Shortest paths: a:- b: (b d 4) c: (c f 2)
    	Costs from a:               8          9
    	Choose (b d 4)
    Step 4:  Shortest paths: a:-  b: (b e 9) c: (c f 2) d: (d f 5)
    	Costs from a:            13         9          13
    	Choose (c f 2)
    Step 5:  Shortest paths: a:-  b: (b e 9) c: (c e 16) d:- f: (e f 3)
    	Costs from a:             13          23           12        
    	Choose (e f 3)
    
    So the final "chain" is (a b 4) (b c 3) (b d 4) (c f 2) (e f 3)
    
    

  3. a) degree =4, since there are four edges that are adjacent to node b.
    b) yes: a b d f e c a (touches all nodes without repeating any) -
    probably there are many others.
    c)  no.  nodes f and e have odd degree, violating Euler's proof conditions
    
  4. first you must calculate the distances, then select the largest distance. Finding the shortest elementary chain for each item will also tell you the distances from the designated item to each item. There are other algorithms as well. Here is the distance matrix:
      B  C  D  E  F
    A 4  7  8 12  9
    B    3  4  8  5
    C       7  5  2
    D          8  5
    E             3
    
    
    Thus, the longest distance is 12, from A to E, and so the diameter of the graph is 12.

  5. No, there is an edge missing from F to D. Thus the graph in this problem must be a directed graph since there is an asymmetry in some edge(s). If the graph in (1) is seen as undirected, then this edge is missing from the graph in (5). If the graph in (1) is seen as directed, then many other edges are missing. In either case, there is no isomorphism that associates every node of (1) with a node of (5) and every edge of (1) with an edge of (5), with no nodes or edges left over.

  6. Here, you were supposed to follow the same algorithm presented in class: ls21-23.There are Several sorts possible.
     Here is the initial data structure you achieve by taking each edge
     and adding one to the count of the "to" node, while putting the 'to"
     node on the list of to nodes for the from node:
    1: 0; 3,5
    2: 3;
    3: 1; 5,6,4
    4: 2; 2
    5: 2; 4,2
    6: 1; 2
    
    Now the algorithm is to simply take (the first) node with a zero count
    and decrement all the counts on the nodes it points to.
    Since 1 is has the only zero count, we start with that, then update
    the DS:
    Sort = 1
    2: 3;
    3: 0; 5,6,4
    4: 2; 2
    5: 1; 4,2
    6: 1; 2
    
    Now we must pick 3:
    Sort = 1,3
    2: 3;
    4: 1; 2
    5: 0; 4,2
    6: 0; 2
    
    
    
    Now we could pick either 5 or 6. Assume 5.
    Sort = 1,3,5
    2: 2;
    4: 0; 2
    6: 0; 2
    
    Now could pick 4 or 6. Assume 6.
     Sort = 1,3,5,6
    2: 1;
    4: 0; 2
    Now we must pick 4.
     Sort = 1,3,5,6,4
    2: 0;
    Now we must pick 2.
    Sort = = 1,3,5,6,4,2
    
    Other possible sorts:
    1,3,5,4,6,2
    1,3,6,5,4,2