CMSC 420 Answers to Selected Questions in Written Asst 2

 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.

 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)



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

 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.

 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.


 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