Unit VI: Graph Theory and Network Models

A graph $G = (V, E)$ is a mathematical structure consisting of a non-empty set of vertices ($V$, or nodes) and a set of edges ($E$, or arcs) that connect pairs of vertices.

   (A)---------(B)       Vertex Set V = {A, B, C}
    |         /          Edge Set E = {(A,B), (B,C), (A,C)}
    |        /           Degree of Vertex A = 2
    |       /
   (C)-----/             Connected Graph

Key Structural Terms

• Adjacent Vertices: Two nodes connected directly by a shared edge.
• Loop: An edge that connects a vertex to itself.
• Degree of a Vertex: The total number of edges connected to a specific vertex.
• Path: A sequence of connected vertices where no edge is repeated.
• Circuit: A path that begins and ends at the exact same vertex.
• Connected Graph: A graph where a continuous path exists between any pair of vertices.
• Bridge: An edge in a connected graph whose removal disconnects the graph.

Eulerian Frameworks

• Euler Path: A path that traverses every single edge in a graph exactly once.
• Euler Circuit: A circuit that traverses every edge in a graph exactly once and returns to the starting vertex.

Euler's Graph Theorems

• A connected graph has an Euler Circuit if and only if the degree of every single vertex is even.
• A connected graph has an Euler Path if and only if it has exactly two vertices with an odd degree. The path must start at one of these odd-degree vertices and end at the other.
• The sum of the degrees of all vertices in any graph equals twice the total number of edges. Consequently, the number of vertices with an odd degree must be even.

Fleury's Algorithm

Used to find an Euler circuit or path in an eligible graph: Start at an appropriate vertex (an odd-degree vertex if finding a path). Traverse edges one by one, following a key rule: never cross a bridge edge unless there are no other remaining options.

• Hamilton Path: A path that visits every vertex in a graph exactly once.
• Hamilton Circuit: A circuit that visits every vertex in a graph exactly once and returns to the starting vertex.
• Complete Graph ($K_n$): A graph with $n$ vertices where every vertex is directly connected to every other vertex.
• Traveling Salesman Problem: The goal of finding a Hamilton circuit in a weighted complete graph that minimizes the total edge weight (cost, distance, or time).

         (B)             Brute Force: List every circuit
      5 / | \ 6          Nearest Neighbor: Always pick closest unvisited node
       /  |  \           Cheapest Link: Sort all edges, pick lowest without
     (A)  |7 (C)                        creating premature circuits or
       \  |  /                          vertex degrees > 2
      4 \ | / 3
         (D)

Algorithms for Solving TSPs

• Brute Force Method: List every possible Hamilton circuit, calculate the total weight of each, and select the one with the lowest sum. This guarantees an optimal solution but becomes inefficient as the number of vertices grows.
• Nearest Neighbor Method: Start at a designated vertex, then move to the nearest unvisited vertex. Repeat this process until all vertices are visited, then return to the start. This provides a fast, approximate solution.
• Cheapest Link Algorithm: Sort all edges in the graph by weight from smallest to largest. Select the shortest available edge, provided it does not create a closed circuit before all vertices are visited, and does not give a single vertex a degree greater than two. Repeat until a complete circuit is formed.

A tree is a connected graph that contains no circuits. A tree with $n$ vertices always contains exactly $n-1$ edges, and every single edge functions as a structural bridge.

• Spanning Tree: A subgraph that connects all vertices of the original graph while forming a tree structure.
• Minimum Spanning Tree (MST): In a weighted graph, the spanning tree that has the lowest possible total edge weight.

Kruskal's Algorithm

Used to find the Minimum Spanning Tree of a weighted graph:

1. Identify the edge with the lowest weight in the graph and select it.
2. Select the next lowest weight edge that does not form a closed circuit with your already selected edges.
3. Repeat this process until all vertices are connected in a single tree structure.

A graph is planar if it can be drawn on a flat plane without any of its edges crossing over each other.

• Graph Coloring: Assigning colors to the vertices of a graph such that no two adjacent vertices share the same color.
• Chromatic Number: The minimum number of colors required to properly color a graph.

           (Color 1)               Vertex Coloring Rules:
            /     \                 1. Pick highest degree node
           /       \                2. Color non-adjacent nodes same color
       (Color 2)---(Color 3)        3. Repeat for remaining nodes

The Four-Color Theorem

Every planar graph (and by extension, any standard geographic map) can be colored using at most four distinct colors such that no two adjacent regions share the same color.