Chapter 10. Concepts of Graph

A graph is a generalization of a tree. In a tree, every node has one parent. In a graph, a node can have multiple parents. The most common way to think about a graph is as a set of vertices and edges. Vertices are like points and edges are like lines that connect the points. In the generic notion of a graph, there is no restriction on which vertices can be connected by edges. This allows graphs to model a versatile category of real-life concepts. The Internet, for example, is a graph where the vertices are the web pages and the edges the hyperlinks between the pages. A social networking site, such as Facebook, has a graph of profiles in which the vertices are the profiles and the edges the friendships between the profiles. Each software has a graph of dependencies, called a dependency graph, in which the vertices are the different software libraries used and the edges the dependencies between the software libraries. There is no end to examples of graphs. In...