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.