Graphs and Their Applications
The Vocabulary and Representation of Graphs
Explained by: Robert I.
Vocabulary:
Vertex- The line segment of a graph.
Vertices- The points of a graph.
-A graph is considered connected if there is a path between each pair of vertices.
-A graph is considered complete if every pair of vertices is adjacent.
*Adjacent means that they are connected!
*The graph above is considered a connected graph since all the vertices are connected!
*The graph above is also considered complete because its vertices are adjacent!
| A | B | C | D | |
| A | 0 | 1 | 0 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
-Above is an adjacency matrix for the previous graph.
-An adjacency matrix is a matrix that shows which vertices are adjacent to each other.
If an edge connects a vertex to itself, it is called a loop. (Example: above)
Euler Circuits and Paths
Vocabulary:
Vertex- The line segment of a graph.
Vertices- The points of a graph.
Euler circuit: A path that uses each edge of a graph exactly once and ends at the starting vertex.
* This is an example of a Euler circuit.
Euler Path: A path were it is possible to use each edge of a graph exactly once but to end at a vertex different from a starting vertex.
*This is an example of a Euler path.
Euler Circuit Algorith- the following chart gives a procedure for finding an Euler circuit for a connected graph with all vertices of even degree.
| 1. | Pick any vertex, and label it S |
| 2. | Construct a circuit, C, that begins and ends at S |
| 3. | If C is a circuit that includes all edges of the graph, go to step 8 |
| 4. | Choose a vertex, V, that is in C and has an edge that is not in C |
| 5. | Construct a circuit C' that starts and ends at V using edges not in C |
| 6. | Combine C and C' to form a new circuit. Call this new circuit C |
| 7. | Go to step 3 |
| 8. | Stop. C is an Euler circuit for the graph |
Graph Coloring
*The purpose of graph coloring is so labeling graphs is an easy process, and the graph will not be confusing to anyone. (Using the minimum number is the most important idea).
*The Chromatic Number is the minimum number of labels or colors that can be used.
*Above is an example of graph coloring. The letters A-C represent the chromatic number which is three, because it only uses 3 numbers or letters in this case. All this means is that you can assign three different colors to A, B, and C so that the graph can not be confused.
Quote: (Concerning the SHS student/faculty game)
"I came, I conquered, and the SENIORS won!" R.I.
This quote represents the character trait of courage, courage is my favorite quote because it is a must have in everyday life.
*Page created by R.I. with pictures from www.bellsnwhistles.com