6.1: Graph Theory
- Page ID
- 22338
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
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.