Graph Theory Worksheet Math 105 Fall 2010 Answers

Graph theory, a vibrant area of mathematics, explores the properties and applications of graphs—structures composed of nodes (vertices) connected by edges. In mathematics courses such as Math 105, particularly in the Fall of 2010, graph theory worksheets provided students with practical exercises to solidify their understanding. While specific answer keys for those worksheets may be unavailable, this article will delve into common graph theory problems and methodologies relevant to such exercises, ensuring a comprehensive grasp of the concepts.

Understanding Graph Theory Basics

Before tackling complex problems, it's crucial to understand the fundamental definitions and concepts in graph theory.

• Graph: A graph G is defined as an ordered pair G = (V, E), where V is a set of vertices (nodes), and E is a set of edges connecting these vertices.
• Vertex (Node): A fundamental unit in a graph, often represented as a point or circle.
• Edge: A connection between two vertices. An edge can be directed (in digraphs) or undirected.
• Directed Graph (Digraph): A graph where the edges have a direction, indicated by an arrow.
• Undirected Graph: A graph where the edges have no direction.
• Adjacent Vertices: Two vertices are adjacent if they are connected by an edge.
• Degree of a Vertex: The number of edges connected to a vertex. In digraphs, we distinguish between in-degree (incoming edges) and out-degree (outgoing edges).
• Path: A sequence of vertices connected by edges.
• Cycle: A path that starts and ends at the same vertex.
• Connected Graph: A graph where there is a path between every pair of vertices.
• Complete Graph: A graph where every pair of vertices is connected by an edge.
• Weighted Graph: A graph where each edge is assigned a weight or cost.

Common Graph Theory Problems and Solutions

Graph theory worksheets typically cover a range of problem types. Let's explore some common ones with illustrative examples.

1. Graph Representation

Representing graphs can be done in several ways, including adjacency matrices and adjacency lists.

Adjacency Matrix: An n x n matrix (where n is the number of vertices) representing the connections between vertices. If there is an edge between vertex i and vertex j, the entry in the i-th row and j-th column is 1 (or the weight of the edge in a weighted graph); otherwise, it's 0.

Adjacency List: A list where each vertex is associated with a list of its adjacent vertices.

Example:

Consider a graph with vertices A, B, C, and D, and edges (A, B), (A, C), (B, C), and (C, D).

Adjacency Matrix:

   A B C D
A  0 1 1 0
B  1 0 1 0
C  1 1 0 1
D  0 0 1 0

Adjacency List:

• A: [B, C]
• B: [A, C]
• C: [A, B, D]
• D: [C]

2. Path Finding

Finding paths between vertices is a fundamental problem. Algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) are commonly used.

Breadth-First Search (BFS): Explores the graph layer by layer, starting from a source vertex. It uses a queue to keep track of vertices to visit.

Depth-First Search (DFS): Explores the graph by going as deep as possible along each branch before backtracking. It uses a stack (implicitly through recursion) to keep track of vertices to visit.

Example:

Find a path from vertex A to vertex D in the graph above using BFS.

1. Start at A. Enqueue A.
2. Dequeue A. Visit A. Enqueue neighbors of A: B and C.
3. Dequeue B. Visit B. Enqueue neighbors of B: A and C (A is already visited).
4. Dequeue C. Visit C. Enqueue neighbors of C: A, B, and D (A and B are already visited).
5. Dequeue D. Visit D. Path found: A -> C -> D.

3. Connectivity

Determining whether a graph is connected or finding connected components is another common task.

Connected Component: A subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

Algorithm: Use BFS or DFS to explore the graph starting from an arbitrary vertex. If all vertices are visited, the graph is connected. Otherwise, repeat the process from an unvisited vertex to find another connected component.

Example:

Consider a graph with vertices A, B, C, D, E, and F, and edges (A, B), (B, C), and (E, F).

• Starting from A, BFS or DFS will visit A, B, and C.
• Starting from E, BFS or DFS will visit E and F.
• Thus, there are two connected components: {A, B, C} and {E, F}.

4. Euler Paths and Circuits

An Euler path is a path that visits every edge exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex.

Theorem:

• A graph has an Euler circuit if and only if every vertex has an even degree.
• A graph has an Euler path if and only if it has exactly two vertices with odd degrees.

Example:

Consider a graph with vertices A, B, C, and D, and edges (A, B), (B, C), (C, D), and (D, A). Each vertex has a degree of 2 (even), so it has an Euler circuit. One possible Euler circuit is A -> B -> C -> D -> A.

5. Hamiltonian Paths and Cycles

A Hamiltonian path is a path that visits every vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that starts and ends at the same vertex.

Unlike Euler paths and circuits, there is no simple theorem to determine whether a graph has a Hamiltonian path or cycle. The problem is NP-complete.

Example:

Consider a complete graph with vertices A, B, and C. A Hamiltonian cycle is A -> B -> C -> A.

6. Minimum Spanning Trees (MST)

Given a weighted graph, a minimum spanning tree (MST) is a tree that connects all vertices with the minimum possible total edge weight.

Algorithms:

• Kruskal's Algorithm: Sorts edges by weight and adds them to the MST if they don't create a cycle.
• Prim's Algorithm: Starts from a vertex and grows the MST by adding the minimum-weight edge that connects the MST to a new vertex.

Example:

Consider a graph with vertices A, B, C, and D, and edges (A, B, 1), (A, C, 2), (B, C, 3), (B, D, 4), and (C, D, 5), where the third value is the weight.

Using Kruskal's Algorithm:

1. Sort edges by weight: (A, B, 1), (A, C, 2), (B, C, 3), (B, D, 4), (C, D, 5).
2. Add (A, B, 1) to the MST.
3. Add (A, C, 2) to the MST.
4. Add (B, C, 3)? No, it creates a cycle (A -> B -> C -> A).
5. Add (B, D, 4) to the MST.
6. The MST is {(A, B, 1), (A, C, 2), (B, D, 4)} with a total weight of 7.

7. Graph Coloring

Graph coloring involves assigning colors to the vertices of a graph such that no two adjacent vertices have the same color. The chromatic number is the minimum number of colors needed to color the graph.

Example:

Consider a graph with vertices A, B, and C, and edges (A, B) and (B, C).

• Color A with color 1.
• Color B with color 2 (since it's adjacent to A).
• Color C with color 1 (since it's adjacent to B but not A).
• The chromatic number is 2.

Deeper Dive into Graph Theory Concepts

Expanding on the basic problems, some additional concepts often appear in graph theory worksheets.

Planar Graphs

A planar graph is a graph that can be drawn on a plane without any edges crossing.

Euler's Formula for Planar Graphs: For a connected planar graph, v - e + f = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces (regions).

Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (complete graph with 5 vertices) or K3,3 (complete bipartite graph with 3 vertices in each part).

Bipartite Graphs

A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V.

Theorem: A graph is bipartite if and only if it contains no odd-length cycles.

Network Flows

Network flow problems involve finding the maximum flow through a network (a directed graph with capacities on the edges) from a source vertex to a sink vertex.

Ford-Fulkerson Algorithm: An iterative algorithm that finds augmenting paths (paths from source to sink with available capacity) and increases the flow along these paths until no more augmenting paths exist.

Graph Isomorphism

Two graphs are isomorphic if they are structurally the same, even if their vertex labels are different.

Determining graph isomorphism is a difficult problem in general. Common techniques include comparing vertex degrees, adjacency matrices, and other graph invariants.

Practical Applications of Graph Theory

Graph theory isn't just an abstract mathematical concept; it has numerous practical applications across various fields.

• Computer Science: Network design, algorithm development, data structures, compiler optimization.
• Social Sciences: Social network analysis, community detection, influence maximization.
• Operations Research: Transportation planning, logistics, scheduling, resource allocation.
• Chemistry: Molecular structure analysis, chemical reaction networks.
• Biology: Gene regulatory networks, protein-protein interaction networks.
• Electrical Engineering: Circuit design, communication networks.

Solving Graph Theory Problems: A Step-by-Step Approach

Tackling graph theory problems effectively requires a systematic approach:

1. Understand the Problem: Clearly define what the problem is asking. Identify the given information (e.g., graph structure, edge weights) and the desired outcome (e.g., shortest path, minimum spanning tree).
2. Choose the Right Representation: Select the most appropriate graph representation (adjacency matrix or adjacency list) based on the problem's requirements. Adjacency lists are often more efficient for sparse graphs (graphs with relatively few edges), while adjacency matrices are better for dense graphs.
3. Select an Algorithm: Choose the appropriate algorithm based on the problem type. For example, use BFS or DFS for path finding, Kruskal's or Prim's for MST, and Ford-Fulkerson for network flows.
4. Implement the Algorithm: Carefully implement the chosen algorithm, paying attention to details such as data structures and edge cases.
5. Test and Debug: Thoroughly test the algorithm with various inputs to ensure its correctness. Use small examples to manually trace the algorithm's execution and identify any bugs.
6. Analyze the Results: Interpret the results in the context of the original problem. For example, if finding the shortest path, verify that the path is indeed the shortest and that it meets any additional constraints.

Example Problems and Detailed Solutions

To further illustrate these concepts, let's work through some example problems similar to those found in a Math 105 graph theory worksheet.

Problem 1: Finding the Shortest Path

Given the following weighted graph, find the shortest path from vertex A to vertex F using Dijkstra's algorithm.

Graph:
A --(4)-- B
A --(2)-- C
B --(1)-- C
B --(5)-- D
C --(8)-- E
D --(2)-- E
D --(3)-- F
E --(1)-- F

Solution:

Dijkstra's algorithm is used to find the shortest path from a source vertex to all other vertices in a weighted graph.

1. Initialization:

   • Distance to A: 0
   • Distance to all other vertices: ∞
   • Unvisited set: {A, B, C, D, E, F}

2. Iteration:

   • A:

     • Visit A.
     • Distance to B: 0 + 4 = 4
     • Distance to C: 0 + 2 = 2
     • Update distances: B=4, C=2
     • Mark A as visited.

   • C:

     • Visit C (shortest distance among unvisited).
     • Distance to B: 2 + 1 = 3 (shorter than 4)
     • Distance to E: 2 + 8 = 10
     • Update distances: B=3, E=10
     • Mark C as visited.

   • B:

     • Visit B (shortest distance among unvisited).
     • Distance to D: 3 + 5 = 8
     • Update distance: D=8
     • Mark B as visited.

   • D:

     • Visit D (shortest distance among unvisited).
     • Distance to E: 8 + 2 = 10 (equal to current distance)
     • Distance to F: 8 + 3 = 11
     • Update distance: F=11
     • Mark D as visited.

   • E:

     • Visit E (shortest distance among unvisited).
     • Distance to F: 10 + 1 = 11 (equal to current distance)
     • Mark E as visited.

   • F:

     • Visit F (shortest distance among unvisited).
     • Mark F as visited.

3. Shortest Path:

   • The shortest distance from A to F is 11.
   • To find the path, trace back from F:
     • F came from E (E -> F = 1)
     • E came from C (C -> E = 8)
     • C came from A (A -> C = 2)
   • Shortest Path: A -> C -> E -> F

Problem 2: Finding a Minimum Spanning Tree

Given the same weighted graph as above, find a minimum spanning tree using Prim's algorithm, starting from vertex A.

Solution:

Prim's algorithm grows a minimum spanning tree from a starting vertex.

1. Initialization:

   • Start at vertex A.
   • MST: {}

2. Iteration:

   • A:

     • Minimum edge from A: (A, C, 2)
     • Add (A, C, 2) to MST.
     • MST: {(A, C, 2)}

   • C:

     • Minimum edge from {A, C} to outside: (B, C, 1) *Note: Considering edges (A,B,4), (C,B,1), (C,E,8). (C,B,1) is the smallest
     • Add (C, B, 1) to MST.
     • MST: {(A, C, 2), (C, B, 1)}

   • B:

     • Minimum edge from {A, B, C} to outside: (B, D, 5) *Note: Considering edges (B,D,5).
     • Add (B, D, 5) to MST.
     • MST: {(A, C, 2), (C, B, 1), (B, D, 5)}

   • D:

     • Minimum edge from {A, B, C, D} to outside: (D, E, 2) *Note: Considering edges (D,E,2), (D,F,3). (D,E,2) is the smallest
     • Add (D, E, 2) to MST.
     • MST: {(A, C, 2), (C, B, 1), (B, D, 5), (D, E, 2)}

   • E:

     • Minimum edge from {A, B, C, D, E} to outside: (E, F, 1) *Note: Considering edges (E,F,1)
     • Add (E, F, 1) to MST.
     • MST: {(A, C, 2), (C, B, 1), (B, D, 5), (D, E, 2), (E, F, 1)}

3. Minimum Spanning Tree:

   • MST: {(A, C, 2), (C, B, 1), (B, D, 5), (D, E, 2), (E, F, 1)}
   • Total weight: 2 + 1 + 5 + 2 + 1 = 11

Problem 3: Determining if a Graph is Bipartite

Determine whether the following graph is bipartite:

Graph:
A -- B
A -- C
B -- C
B -- D
C -- E
D -- F
E -- F

Solution:

A graph is bipartite if and only if it contains no odd-length cycles.

1. Coloring Approach:
   • Start with vertex A and color it color 1.
   • Color B and C with color 2 (since they are adjacent to A).
   • Since B and C are adjacent, the graph is not bipartite (odd-length cycle A-B-C-A).
2. Cycle Detection Approach:
   • The graph contains the cycle A-B-C-A which has length 3 (odd)
   • Therefore the graph is not bipartite

Conclusion:

The graph is not bipartite because it contains an odd-length cycle (A-B-C-A).

Conclusion

Graph theory provides a powerful framework for modeling and solving a wide range of problems. By understanding the fundamental concepts, algorithms, and problem-solving techniques discussed in this article, students of Math 105 and similar courses can effectively tackle graph theory worksheets and gain a solid foundation in this important area of mathematics. While specific answer keys for the Math 105 Fall 2010 worksheets may not be available, the methodologies and examples provided here offer a comprehensive guide to mastering graph theory problems.