Broken Graphs, Part I
Is it possible for graphs to come in individual pieces? Is it possible to take a graph and break it into multiple pieces? What implications does this have in real world applications?
|
|
|
What You Should LearnConnected means exactly what the English word suggests. Two points are connected if there's a path from one to the other. A graph is connected if it has only "one piece". |
All that business about "a function that maps ..." just means that each edge is assigned a number. |
Both of the graphs below are disconnected. It's obvious that the first one is because it's made up of two completely distinct pieces. (If you want a technical reason it's disconnected because there's no path from v1 to v3, among others.) The second graph is a little less clear because of the way the graphs overlap but, if you look closely, you'll see that there's no path from v5 to v8.
 |
 |
If G is a graph and e is an edge in G then G - e is G with edge e removed. Similary if v is a vertex of G then G - v is G with the vertex v and every edge that connected to it removed. Now assume that G is connected. If G - e is disconnected then e is called a bridge. If G - v is disconnected then v is called a cut-vertex. |
The subtraction symbol, - , has the same idea of "taking away" with graphs that it does with numbers. G - e means the graph G with edge e "subtracted" or "taken away". The same idea applies to vertices only you also have to take away all of the edges that connected to the vertex. A graph theory bridge is also similar to its English equivalent. You can think of it as a connector between two graphs that would be disconnected if the bridge weren't there. Just like two islands become disconnected if the bridge connecting them is removed. |