mkse150   Homework 1

Answers

Text book exercise 2.5.1:
(a) Any circle of size n>4. Each node is pivotal for the pair consisting of its right and left neighbor.
(b) Any circle of size n>6. Each node is pivotal for the pair consisting of its right and left neighbor, and the pair consisting of its right neighbor and the left neighbor of its left neighbor.
(c) Any star network of size n>3. The center node is pivotal to every pair of vertices in the graph(off course not including the center node itself), because there is no other path between two vertices other than passing through the center.

Text book exercise 3.7.3:
Only C and E do not satisfy the property.

Text book exercise 3.7.4:
Only C and E do not satisfy the property.

Text book exercise 3.7.5:
Only C does not satisfy the property.

Text book exercise 5.6.4:
Consider the farmers at places 1, 25, and 50. It is easy to see that every pair of them are enemies, as each one of them lives more than 20 miles from the other two. Therefore the graph is not structurally balanced.

Breadth-First Search programming problem:

	public void explore(String startNode, int depthLimit) {
		this.startNode= startNode;
		Queue<String> queue= new LinkedList<String>();	// queue of nodes to examine
		depth= new HashMap<String,Integer>();
		queue.add(startNode);
		depth.put(startNode,0);
		while (queue.size()>0) {
			String node= queue.remove();
			Integer parentDepth= depth.get(node);
			//System.out.print("exploring "+node+" "+parentDepth+": ");
			if (parentDepth>depthLimit) break;
			Set<String> nhbrs= graph.getNeighbors(node);
			for (String nhbr : nhbrs) {
				//System.out.print("   "+nhbr);
				if(depth.get(nhbr)==null) { queue.add(nhbr); depth.put(nhbr, parentDepth+1); } 
			}
			//System.out.println();
		}
	}

Counting Shortest Paths programming problem:

	public void countPaths() {
		spCount= new HashMap<String,Integer>();
		spCount.put(startNode, 1);
		Set<String> prevLevelNodes= this.getNodesAtDepth(0);
		for (int levelNumber=1; ; levelNumber++) {
			Set<String> nextLevelNodes= this.getNodesAtDepth(levelNumber);
			if (nextLevelNodes.size()==0) break;
			for (String next : nextLevelNodes) {
				Set<String> nhbrs= graph.getNeighbors(next);
				nhbrs.retainAll(prevLevelNodes);// leaves nhbrs as intersection of itself and prevLevelNodes
				int count= 0;
				for (String prev : nhbrs) count+= spCount.get(prev);
				spCount.put(next,count);
			}
			prevLevelNodes= nextLevelNodes;	// exchanges *handles*; does not copy data
		}
	}

Extra credit text book exercise 5.6.4: