Essential Concepts

• Graphs and multigraphs represent objects as vertices and the relationships between the objects as edges.
• The degree of a vertex is the number of edges that meet it and the degree can be zero.
• An edge must have a vertex at each end. A loop is a special type of edge that connects a vertex to itself. 
• Multigraphs may contain loops and double edges, but simple graphs may not.
• In a connected graph there is a path from any vertex to any other vertex.
• A subgraph is part of a larger graph.
• Paths are ways to navigate through a graph using a sequence of connected vertices and edges.
• Circuits are ways to navigate from a vertex on a graph and return to the same vertex.
• Depending upon the problem being solved, sometimes weights are assigned to the edges. The weights could represent the distance between two locations, the travel time, or the travel cost
• The Euler circuit theorem states that an Euler circuit exists in every connected graph in which all vertices have even degree, but not in disconnected graphs or any graph with one or more vertices of odd degree.
• Fleury’s Algorithm is the formal method used to determine if a graph has an Euler circuit.
• Eulerization is the process of adding duplicate edges to a graph so that the new multigraph has an Euler circuit.
• The minimum number of duplicated edges needed to eulerize a graph is half the number of odd vertices or more.
• An Euler path exists whenever a graph has exactly two vertices of odd degree.
• The Chinese postman problem asks how to find the shortest closed trail that visits all edges at least once.
• A Hamilton circuit is a circuit that visits every vertex once with no repeats.  Being a circuit, it must start and end at the same vertex.
• A Hamiltonian path visits every vertex once with no repeats, but does not have to start and end at the same vertex.
• A brute force algorithm always finds the ideal solution but can be impractical whereas a greedy algorithm is efficient but usually does not lead to the ideal solution.
• A Hamilton circuit of lowest weight is a solution to the traveling salesperson problem.
• The brute force method finds a Hamilton circuit of lowest weight in a complete graph.
• The nearest neighbor method is a greedy algorithm that finds a Hamilton circuit of relatively low weight in a complete graph.
• The Sorted Edges Algorithm focuses on constructing a circuit (or a path) that includes all vertices in a graph by selecting the least expensive edges while avoiding premature circuits and ensuring that no vertex has more than two edges connected to it.
• A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree (a connected graph with no cycles). A spanning tree connects all vertices with the minimum possible number of edges.
• A single graph can have multiple different spanning trees.
• A minimum cost spanning tree is a spanning tree with the minimum total edge weight among all possible spanning trees of a weighted graph.
• Kruskal’s Algorithm is a popular method to find the MCST of a graph.

Glossary

algorithm

a step-by-step procedure for solving a problem

circuit

a path that begins and ends at the same vertex

degree of a vertex

the number of edges meeting at that vertex

edges

connect pairs of vertices

Euler circuit

a circuit that uses every edge in a graph with no repeats

Euler path

a path that uses every edge in a graph with no repeats

Eulerization

the process of adding edges to a graph to create an Euler circuit on a graph

graph

consists of vertices and a set of edges connecting pairs of vertices

Hamiltonian circuit

a circuit that visits every vertex once with no repeats that starts and ends at the same vertex

Hamiltonian path

a path that visits every vertex once with no repeats, but does not have to start and end at the same vertex

loop

a special type of edge that connects a vertex to itself

minimum cost spanning tree

the spanning tree with the smallest total edge weight

optimal algorithm

an algorithm that always produces the actual shortest path, not just a path that is pretty short, provided one exists

path

a sequence of vertices such that each vertex is adjacent to the next one

spanning tree

a connected graph using all vertices in which there are no circuits

vertex

a dot in the graph that could represent an intersection of streets, a land mass, or a general location

weights

assigned to the edges, could represent the distance between two locations, the travel time, or the travel cost

Key Equations

Number of Possible Circuits

[latex]\frac{(n-1)!}{2}[/latex]