6.1: Graph Theory
- Page ID
- 22338
There are several definitions that are important to understand before delving into Graph Theory. They are:
- A graph is a picture of dots called vertices and lines called edges.
- An edge that starts and ends at the same vertex is called a loop.
- If there are two or more edges directly connecting the same two vertices, then these edges are called multiple edges.
- If there is a way to get from one vertex of a graph to all the other vertices of the graph, then the graph is connected.
- If there is even one vertex of a graph that cannot be reached from every other vertex, then the graph is disconnected.
In the above graph, the vertices are U, V, W, and Z and the edges are UV, VV, VW, UW, WZ1, and WZ2.
This is a connected graph. VV is a loop. WZ1, and WZ2 are multiple edges.
The graph in Figure \(\PageIndex{2}\) is connected while the graph in Figure \(\PageIndex{3}\) is disconnected.
- Order of a Network: the number of vertices in the entire network or graph
- Adjacent Vertices: two vertices that are connected by an edge
- Adjacent Edges: two edges that share a common vertex
- Degree of a Vertex: the number of edges at that vertex
- Path: a sequence of vertices with each vertex adjacent to the next one that starts and ends at different vertices and travels over any edge only once
- Circuit: a path that starts and ends at the same vertex
- Bridge: an edge such that if it were removed from a connected graph, the graph would become disconnected
In the above graph the following is true:
- Vertex A is adjacent to vertex B, vertex C, vertex D, and vertex E.
- Vertex F is adjacent to vertex C, and vertex D.
- Edge DF is adjacent to edge BD, edge AD, edge CF, and edge DE.
The degrees of the vertices:
A | 4 |
B | 4 |
C | 4 |
D | 4 |
E | 4 |
F | 2 |
Here are some paths in the above graph: (there are many more than listed)
A,B,D
A,B,C,E
F,D,E,B,C
Here are some circuits in the above graph: (there are many more than listed)
B,A,D,B
B,C,F,D,B
F,C, E, D, F
The above graph does not have any bridges.