This section defines graphs, their components, some special types of graphs, and illuminates many of their properties. It talks about some of the applications of graphs and some of the real-world concepts they can model: transportation, communication, information, social, and dependency networks. It defines “path” (any set of connected nodes), “connectivity” (if there exists a path between two nodes) in terms of both directed and undirected graphs, and “distance”. It introduces trees and explains that removing a node from a tree makes it disconnected, and also the fancy thing we talked about in class about the three connected/no cycle/n-1 edges thing implying eachother, but doesn't prove it–glad we did it in class, it was fun. Spoke briefly about how trees are particularly appropriate for representing the “hierarchical” nature of things. Which is kind of like, duh, but I had never explicitly realized that before.

I'd say 8/10 readability–though I had been introduced to most of the concepts already, and I had already been through lecture before I read the textbook. (Am I supposed to read in the other order?) So the most difficult part of reading was not getting bored.

This section explores breadth-first and depth-first search. Breadth-first search produces “layers” and operates like a flood of water spreading forth from the source to all the nodes, giving you information about the shortest path from the source to each node. Depth first search operates like a person in a maze with “dead-ends” and yields information about whether nodes have an ancestor-descendant relationship going on. Along the way, it goes through that generic search algorithm where you just keep adding nodes that are connected by edges and haven't been added yet (but doesn't tell you how to pick which nodes.) The section then talks about the connected components of the graph and goes through the proof that if there's a path between two nodes they have to be connected.

8/10 readability here too, pretty much the same as last section.

This section applies data structures to graphs and breadth-first and depth-first search. It overviews the two ways of representing a graph and analyzes their space requirement bounds (O(n^2) for adjacency matrix, and O(m+n) for adjacency lists). After giving a short introduction to queues and stack, it then goes through O(m+n) implementations of depth-first search using a list to contain the layers, and breadth-first search using a stack. Points out the similarity between the Discovered[] of BFS and the Explored of DFS[]. The stack DFS operates sdrawkcab from the recursive DFS in the last section–thought that was curious–because recursion means function calls, and function calls are usually implemented with a call stack, so it peculiar there is a difference.

7/10 readability here, same deal as last section. The concepts are a bit more involved, so it took a little time parsing the words until I could make the connection with the corresponding bit of lecture, but it was good to have the review.

This section is a short analysis of the property of bipartiteness. First is a definition–the authors do sort of a funky thing, they define it mathematically with like dividing the nodes into two mathematical 'sets', but then they equate this with some nodes being “red” and others “blue” and just proceed along with that analogy for the remainder of the section. It seems not all textbooks would do that–I appreciate how the authors are not overly obsessed with being all formal. Then there's a thought experiment demonstrating the truth that a bipartite graph cannot contain an odd cycle. Then, explore the problem a little bit more in-depth by applying breadth-first search to it, proving that the odd cycle is the only obstacle to a graphs bipartiteness.

8/10 readability, short, clear, nice to do the color thing.

This section just analyzes the implications of directedness of a graph. Breadth-first search and depth-first search are pretty much as you would expect–the same except they only follow an edge if the edge is heading the right direction, and their return value has a different significance, since it's only a path _to_ a node, and no longer a path both _to_ and _from_ a node. (Though you could reverse it and have it just follow the froms to get the _from_ information.) Then it talks about strong connectivity (mutual reachability) and illuminates some properties (transitivity, a thingy about strong components having to be either connected or disjoint).

8/10 readability, same deal.

This section is mostly about topological orderings. Turns out directed graphs can get pretty fancy and have tons of edges, even without cycles. The authors prove that every directed graph without cycles can be put into a “topological ordering” which looks like a line of nodes, with all the edges pointing one direction. They prove this, and they come up with an algorithm to find such an ordering. First they do it in O(n^2), and then in O(n+m) by keeping track for each node how many edges they have pointing to it and updating as they go along, instead of iterating through each time to find the node with no edges pointing to it.

9/10 readability, this was new material for me but I think I have a pretty full understanding of it and it wasn't very boring. The best part was the picture on the top of 100. I looked at that for a bit and I sort of knew what was coming as the section went along. It truly was worth a thousand words.

Incidentally, it'd be kind of nice if you could update the link to 'Journals' from the main page to _this_ year's set of journals instead of Winter 2011's? I don't think it points to the right place.