Kruskal’s Algorithm and Graph Theory Analysis

Posted on Mar 8, 2025 in Computers

Step 1: Create an Edge List Based on the Given Distances

Step 2: List of Edges Sorted by Distance

• Prague – Plzen: 95
• Prague – Pardubice: 95
• Brno – Olomouc: 80
• Brno – Pardubice: 146
• Tabor – Plzen: 140
• Tabor – Prague: 150
• Pardubice – Olomouc: 140
• Plzen – Tabor: 140
• Brno – Tabor: 180
• Pardubice – Tabor: 210
• Olomouc – Plzen: 372
• Olomouc – Tabor: 273
• Olomouc – Prague: 245
• Brno – Plzen: 280

Step 3: Apply Kruskal’s Algorithm

1. Select the smallest edge (Prague – Plzen, 95): Cities Prague and Plzen are now connected.

2. Next smallest edge (Prague – Pardubice, 95): Cities Prague and Pardubice are now connected.

3. Next smallest edge (Brno – Olomouc, 80): Cities Brno and Olomouc are now connected.

4. Next smallest edge (Brno – Pardubice, 146): Cities Brno and Pardubice are now connected.

5. Next smallest edge (Tabor – Plzen, 140): Cities Tabor and Plzen are now connected.

6. Next smallest edge (Pardubice – Olomouc, 140): Cities Pardubice and Olomouc are now connected.

Step 4: Total MST Construction

The cities connected by these edges are all part of a single tree with no cycles. The highway segments we choose to build are:

• Prague – Plzen (95)
• Prague – Pardubice (95)
• Brno – Olomouc (80)
• Brno – Pardubice (146)
• Tabor – Plzen (140)
• Pardubice – Olomouc (140)

Step 5: Calculate the Total Length of the Roads Built

Total length = 95 + 95 + 80 + 146 + 140 + 140 = 696 units of distance. The total length of the roads built is 696 units.

Final Answer:

To connect all the cities with the least total distance, the highway segments to build are:

• Prague – Plzen (95)
• Prague – Pardubice (95)
• Brno – Olomouc (80)
• Brno – Pardubice (146)
• Tabor – Plzen (140)
• Pardubice – Olomouc (140)

Graph Theory Statements

a) Any Subgraph (with at Least Two Vertices) of a Bipartite Graph is also Bipartite

False.
Counterexample: Consider a bipartite graph with two sets of vertices: U = {u₁, u₂} and V = {v₁, v₂}, where each vertex in U is connected to each vertex in V. Now, take a subgraph that consists of just the edge u₁ to u₂. This subgraph is not bipartite because there are edges within the same set (i.e., between two vertices in U), which breaks the bipartite condition. Therefore, not every subgraph of a bipartite graph is bipartite.

b) Any Eulerian Graph is Connected

True.
For a graph to be Eulerian, it must contain an Eulerian circuit (a cycle that visits each edge exactly once). For such a circuit to exist, the graph must be connected because if the graph were disconnected, there would be no way to visit all edges in one continuous cycle. Thus, all Eulerian graphs are connected.

c) If G is Eulerian, then it Contains a Hamiltonian Cycle

False.
Counterexample: Consider a graph that is Eulerian but does not contain a Hamiltonian cycle. A counterexample is a graph formed by a triangle (3 vertices and 3 edges) and a disjoint vertex (isolated vertex). This graph is Eulerian because all vertices have an even degree, but it does not contain a Hamiltonian cycle because there is no way to visit all vertices exactly once in a cycle. Therefore, an Eulerian graph does not necessarily have a Hamiltonian cycle.

d) If G Contains a Hamiltonian Cycle, then it is Eulerian

False.
Counterexample: Consider a cycle graph C₄ (a square, with 4 vertices and 4 edges). This graph contains a Hamiltonian cycle (a cycle that visits each vertex exactly once), but it is not Eulerian because the degree of each vertex is 2 (even), and a necessary condition for a graph to be Eulerian is that all vertices must have an even degree and the graph must be connected. However, in this case, although the degree condition is satisfied, the graph may not necessarily fulfill the connectivity requirement in all cases (depending on the structure). Hence, it does not imply Eulerian properties based solely on having a Hamiltonian cycle.

e) Let G be a Graph with an Even Number of Vertices. Let M be a Matching in G. If M is Maximal, then M is Perfect

False.
Counterexample: Consider a graph with 4 vertices and edges connecting pairs (v₁, v₂), (v₃, v₄), and no other edges. A maximal matching could be M = {(v₁, v₂)}, but it is not perfect because not all vertices are covered by the matching (vertex v₃ and vertex v₄ are not matched). A maximal matching does not necessarily match every vertex, so it is not always perfect.