Graph Theory: Paths, Circuits, and Algorithms
This flashcard set explores the foundations of graph theory, including definitions of vertices, edges, and degrees. It distinguishes between Euler paths/circuits (which focus on edges) and Hamilton paths/circuits (which focus on vertices). Concepts such as adjacency, connectivity, and weighted graphs are included, as well as Euler’s Theorem and Fleury’s Algorithm for identifying Euler paths or circuits. Practical applications like route planning and network traversal are also covered.
Definition of a graph
A graph consists of a finite set of points, called vertices (singular is vertex), and line segments or curves called edges, that start and end at vertices.
An edge that starts and ends at the same vertex is called a loop.
Key Terms
Definition of a graph
A graph consists of a finite set of points, called vertices (singular is vertex), and line segments or curves called edg...
Degree of vertex
Number of edges at that vertex.
Vertex with even number of edges is “even vertex”. And ...
Adjacent vertices
Two vertices connected by at least one edge.
Adjacent vertices = connected vertices
Circuit
A path that begins and ends on same vertex.
Every circuit is a path. But Not every path...
Connected graph
If for any 2 of its vertices there is at least one path connecting them.
Euler path
A path that travels though every edge of a graph once and only once. Each edge must be traveled and no edge must be retr...
Related Flashcard Decks
Study Tips
- Press F to enter focus mode for distraction-free studying
- Review cards regularly to improve retention
- Try to recall the answer before flipping the card
- Share this deck with friends to study together
| Term | Definition |
|---|---|
Definition of a graph | A graph consists of a finite set of points, called vertices (singular is vertex), and line segments or curves called edges, that start and end at vertices. |
Degree of vertex | Number of edges at that vertex. Vertex with even number of edges is “even vertex”. And odd number of edges is”odd vertex.” |
Adjacent vertices | Two vertices connected by at least one edge. Adjacent vertices = connected vertices |
Circuit | A path that begins and ends on same vertex. Every circuit is a path. But Not every path is a circuit. |
Connected graph | If for any 2 of its vertices there is at least one path connecting them. |
Euler path | A path that travels though every edge of a graph once and only once. Each edge must be traveled and no edge must be retraced. |
Euler circuit | Travels though each edge of graph once and only once and must end on same vertex. |
Euler’s theorem | Following statements are true for connected graphs: |
Fleury’s algorithm -what is the procedure? | 1- If the graph has exactly two odd vertices, choose one of the two vertices as the starting point. If the graph has no odd vertices, choose any vertex as a starting point. |
Purpose of Fleury’s algorithm | Finding A Euler’s path or a Euler’s circuit |
Is a Euler circuit and Euler path the same thing? | Every Euler circuit is a Euler path. However, NOT Every Euler path is a Euler circuit. |
Hamilton path | A path that passes through each vertex of a graph exactly once. |
Hamilton circuit | If a Hamilton path begins and ends at the same vertex and passes through all other vertices exactly once it is a Hamilton circuit. |
Difference between Hamilton path and Euler path | Hamilton path involves vertices. Hamilton paths are used for ups drivers for specific locations. |
Weighted graph | A graph whose edges have numbers attached to them. For example the cost of airfare from city A to city B. |
Traveling sales person problem | The problem of finding a Hamilton circuit in a complete weighted graph For which the sum of the weights of the edges is a minimum. |
Optimal Hamilton circuit | Also known as optimal solution. It is the minimum sum of weights of the edges in a weighted graph. (Traveling sales person problem) |
Brute force method | One method for finding an optimal Hamilton circuit. It uses the following steps: 1-model the problem with a complete weighted graph. 2- make a list of all the possible Hamilton circuits 3- Determine the sum of the weights of the edges for each of these circuits 4- The circuit with the minimum sum of weight is the optimal |
Nearest neighbor method of finding approximate Solutions to the traveling sales person problem | 1-model the problem with the complete weighted graph. 2-Identify the vertex that serves as the starting point. 3- From the starting point, choose the edge with the smallest weight. Go to that vertex 4-Continue building the circuit, one vertex at a time, by moving along the edge with the smallest weight until all vertices are visited. |