Algorithms For Dummies

Understanding subgraphs

Relationships depicted by graphs can become quite complex. For example, when 

depicting  city  streets,  most  streets  allow  traffic  in  both  directions,  making  an 

undirected graph perfect for representation purposes. However, some streets 

allow traffic in only one direction, which means that you need a directed graph in 

this case. The combination of two-way and one-way streets makes representation 

using a single graph type impossible (or at least inconvenient). Mixing undirected 

and directed graphs in a single graph means that you must create subgraphs to 

depict each graph type and then connect the subgraphs in a larger graph. Some 

graphs  that  contain  subgraphs  are  so  common  that  they  have  specific  names, 

which is a mixed graph in this case.

Subgraphs are useful for other purposes as well. For example, you might want to 

analyze a loop within a graph, which means describing that loop as a subgraph. 

You don’t need the entire graph, just the nodes and edges required to perform the 

analysis. All sorts of disciplines use this approach. Yes, developers use it to ensure 

that parts of an application work as expected, but city engineers also use it to 

understand  the  nature  of  traffic  flow  in  a  particularly  busy  section  of  the  city. 

---

CHAPTER 8