Unit 1 Test - Graph Theory Flashcards
Graph definition
A collection of dots and lines or curves connecting pairs of vertices
Vertex definition
Dots
Edge definition
Lines or curves connecting vertices
Loop definition
An edge that connects a vertex to itself
Degree/valence of a vertex meaning
Number of edges meeting at that vertex
Path definition
A sequence of vertices connected by edges
Circuit definition
A closed path, meaning a path that starts and ends at the same vertex
Connected graph definition
Any two vertices have a path connecting them
Weight of an edge meaning
The “cost” of the edge
Euler path definition
A path that uses every path exactly once
Euler circuit definition
A circuit that’s also an Euler path
How can you know if a graph has an Euler circuit?
All vertices have even degrees
Fleury’s Algorithm
Verify the existence of the Euler path or circuit, then start at any vertex (circuit) or a vertex of odd degree (path) and choose any edge leaving that vertex, assuming that deleting that edge doesn’t separate the graph. Add that edge to the circuit/path and delete it from the graph, continuing until complete.
Eulerization definition
The process of adding edges to adjacent vertices to create an Euler circuit
Efficient Eulerization
Minimizing the number of duplicated edges
Chinese Postman Problem
Euler Circuit Theorem
If G is connected and all its vertices have even degree/valence, then G has an Euler circuit (and vice versa)
Euler Path Theorem
If G is connected and exactly two vertices have odd degree, then G has an Euler path and no Euler circuit, and if G has more than 2 vertices with odd degree, then G does not have an Euler path
Valence Theorem
For any graph G, the total number of vertices with odd valence is either zero or an even number
Digraph/Directed graph definition
A graph in which each edge has an arrow that indicates the edge’s direction
Weighted graph definition
A graph in which each edge has a number associated with the edge
Weight of a graph definition
The total number of the weight of each edge
Hamiltonian Path
A path where each vertex is used only once.
Hamiltonian Circuit
A path where each vertex is used only once, other than the start and end vertex
Traveling Salesman Problem
FInding a Hamiltonian circuit of smallest total weight
Traveling Salesman Problem examples
Salesman based in one city traveling to each city in territory once, airport limo picking up customers and taking to airport, technician serving each of a bank’s network of ATMs, postal worker delivering mail to each drop-off box, etc.
Brute force algorithm definition
Find all possible H. circuits and choose the one of smallest weight (time-consuming and inefficient)
Complete graph definition
A graph such that any two distinct vertices are joined by one edge (n vertices, denoted Kn)
Fundamental Principle of Counting
Suppose that we have n stages and at stage i there are ai distinct choices that can be made. Then the total number of choices is… a1 x a2 x a3 …. an
Number of possible Hamiltonian circuits in a complete graph if start vertex matters
n!
Number of possible Hamiltonian circuits in a complete graph if start vertex doesn’t matter
(n-1)!
Number of possible Hamiltonian circuits in a complete graph if start vertex doesn’t matter and direction doesn’t matter
(n-1)! / 2
What types of graphs will never have Hamiltonian circuits?
Bipartite graphs and n x m rectangular graphs with n and m both being odd (# vertices)
Greedy algorithms definition
Algorithms that are locally but not necessarily globally optimal
Heuristic algorithms definition
Algorithms that will produce a solution relatively quickly, but with no guarantee that the solution is optimal
Nearest Neighbor Algorithm definition
Select a starting point, move to the closest unvisited vertex by edge of smallest weight, and repeat until the circuit is completed
Does the NNA always give a Hamiltonian circuit of smallest weight?
No, it may or may not
Repeated Nearest Neighbor Algorithm
Do the NNA for each vertex, then choose the circuit of smallest weight
Sorted Edges Algorithm definition
Select the cheapest unused edge in the graph and repeat unless adding the edge makes a circuit not containing all vertices or adding the edge gives a vertex degree 3
Hamiltonian circuits/paths real-world applications
Road trips/sightseeing, worker checking sites, etc.
Spanning tree definition
A connected graph using all vertices in which there are no circuits
Subgraph definition
Minimum cost spanning tree definition
A spanning tree of smallest weight or cost
Kruskal’s Algorithm
Select the cheapest unused edge in the graph, repeat unless adding the edge would create a circuit, and repeat until a spanning tree is formed (similar to sorted edges)
Does Kruskal’s Algorithm always give a minimal cost spanning tree?
No, it does not always
Prim’s Algorithm
Remove all loops and parallel edges of highest weight, choose any vertex, select an outgoing edge of lowest cost, and repeat for any previously included vertex unless including an edge forms a cycle (similar to NNA)
Does Prim’s Algorithm always give a minimal cost spanning tree?
No, it doesn’t always
Spanning tree real-world applications
Utility lines (water, telephones, electric wiring)
Spanning tree number of edges
A tree with n vertices has n-1 edges
How many spanning trees exist?
Complete graph Kn has n ^n-2 spanning trees
Minimal cost spanning tree real-world applications
Connectivity (utility lines, water pipes, internet cables, etc.), facial recognition software, etc.
Vertex coloring definition
What’s the fewest number of colors needed to not have two vertices have the same color
Chromatic number of a graph
The fewest number of colors needed to color each vertex so that no adjacent vertices have the same color (shown X(G))
Brook’s Theorem
For any graph G, X(G) <= delta (G) unless G is a complete graph or a circuit with an odd number of vertices in which case X(G) = delta (G) + 1
Graph coloring real-world application
Avoiding conflict
What is the lower bound of the chromatic number?
Subgraphs (does it contain k3?, k4?, k5?, etc.)
What is the upper bound of the chromatic number?
The largest degree of any vertice
What is the chromatic number for complete graphs?
Kn = n
What is the chromatic number for tree graphs?
2
What is the chromatic number for bipartite graphs?
2
What is the chromatic number for circuit graphs with even vertices?
2
What is the chromatic number for circuit graphs with odd vertices?
3
