Chapter 3

This chapter introduces us the basic knowledge of graph.

The section first introduces some basic concepts and notations of graph, such as vertex, edge, and orientation of graphs.

Then several examples are illustrated: transportation networks that are tangible, though in practice directed, can be viewed as indirected graph, since the traffic normally comes both ways; Communication networks-basically just connecting computers together and sharing information-are directed graphs, since sometimes computer U hears V's signal but not conversely; information networks have very useful examples such as the WWW internet, where websites are nodes and hyperlinks are edges; social networks display the interactions among people; dependency networks are used in important biological ways such as the food web.

The geometric perspective of the communication networks further interest me-is it like a shortest path problem in nature? In addition, regard WWW as a graph is new to me: I never thought of individual websites as vertices, and hyperlinks to be edges. The directness of the information networks also play a vital rule, such as in prioritizing websites for search engines. How exactly does it work?

Next several more important definitions in graph theories are introduced, such as Paths&Connectivity (simple, cycle; strongly connected, distance), trees (child, parent, descendant, ancestor, leaf…). The text also addresses the importance of trees since they indicate hierarchy. The important theorem (3.2) is also stated.

I'd like to know more about trees, spanning trees, minimum spanning trees, etc.

Readability is 7, since most of the materials are not unfamiliar.

This section describes two natural algorithms for maze-solving problem (s-t connectivity problem).

BFS: The general idea is to fix a node s, and then find all nodes 1 distance away denoted as layer 1, 2 distances away as layer 2, etc… Notice that the BFS tree has some edges of the original graph G erased, such as those edges connecting nodes in the same layers. s and t are connected iff t is in some layer of s and the number of the layer would be the distance between s and t. An important observation is that if a and b constitute an edge, then a and b are either in the same layer or differs by one layer. The text also states a theorem we talked in class, but in a different way: the set produced at the end of the BFS algorithm is precisely the connected component containing the root node.

Question: what are some applications of BFS?

DFS: The basic idea is to list out the first layer as BFS, but then explore specifically at the first node in the layer, list out the second layer from that node, then keep on looking at the first node of that layer, etc… Notice that the DFS tree has some edges erased, in fact the theorem “ let x,y be nodes in T, if (x,y) be anedge of G that is not anedge of T, then one of x or y is an ancestor of the other” generalizes such edges.

Question: what are some applications of DFS?

The end of the section states an important theorem that is an extension, as well as an application, of the last theorem in BFS: For any 2 nodes s and t in a graph, their connected components are either identical or disjoint.

Readability: 7