Understanding the Königsberg Bridge Problem

Historical Background

The Königsberg Bridge Problem is one of the most famous problems in mathematics and is considered the foundation of graph theory and topology. In the early 18th century, the city of Königsberg (now Kaliningrad, Russia) was set on both sides of the Pregel River and included two islands. Seven bridges connected these land masses, and citizens wondered if it was possible to walk through the city crossing each bridge exactly once.

This seemingly simple puzzle caught the attention of mathematician Leonhard Euler in 1736, who solved it by proving that such a walk was impossible and, in doing so, created the first theorem of graph theory.

Key Concepts in Graph Theory

Graph Representation

To approach this problem mathematically, Euler represented the land masses as "vertices" (or nodes) and the bridges as "edges" connecting these vertices. This abstraction transformed a physical problem into a mathematical one, creating what we now call a graph.

Degree of a Vertex

The degree of a vertex is the number of edges connected to it. In the Königsberg bridge problem:

• The mainland areas each had 3 bridges (degree 3)
• The island had 5 bridges (degree 5)

Eulerian Paths and Circuits

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

Euler's Theorem

Euler proved that:

1. A graph has an Eulerian circuit if and only if every vertex has an even degree.
2. A graph has an Eulerian path (but not a circuit) if and only if exactly two vertices have odd degrees.

Why the Königsberg Bridge Problem Has No Solution

In the Königsberg bridge configuration, all four land masses had an odd number of bridges connected to them (degrees 3, 3, 3, and 5). According to Euler's theorem, for an Eulerian path to exist, at most two vertices can have odd degrees. Since all four vertices had odd degrees, it was impossible to create a path crossing each bridge exactly once.

Java Program for the Königsberg Bridge Problem

Here's a detailed Java program that models the Königsberg Bridge Problem and checks whether a graph has an Eulerian path or circuit:

import java.util.*;

/**
 * This class represents the Königsberg Bridge Problem using graph theory concepts.
 * It models the city's land masses as vertices and bridges as edges in a graph,
 * and provides functionality to check if an Eulerian path or circuit exists.
 */
public class KonigsbergBridgeProblem {

    // Number of vertices (land masses) in the graph
    private int vertices;

    // Adjacency list to represent the graph
    private ArrayList<ArrayList<Integer>> adjacencyList;

    /**
     * Constructor to initialize the graph with a specified number of vertices
     * @param vertices The number of vertices (land masses)
     */
    public KonigsbergBridgeProblem(int vertices) {
        this.vertices = vertices;
        this.adjacencyList = new ArrayList<>(vertices);

        // Initialize the adjacency list for each vertex
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    /**
     * Add an undirected edge (bridge) between two vertices (land masses)
     * @param v First vertex (land mass)
     * @param w Second vertex (land mass)
     */
    public void addEdge(int v, int w) {
        // Add edge from v to w and from w to v (undirected graph)
        adjacencyList.get(v).add(w);
        adjacencyList.get(w).add(v);
    }

    /**
     * Check if the graph is connected
     * This is a required condition for an Eulerian path or circuit
     * @return true if the graph is connected, false otherwise
     */
    private boolean isConnected() {
        // Boolean array to mark visited vertices
        boolean[] visited = new boolean[vertices];

        // Find a vertex with non-zero degree
        int startVertex = 0;
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() > 0) {
                startVertex = i;
                break;
            }
        }

        // Perform DFS starting from the vertex found
        dfs(startVertex, visited);

        // Check if all vertices with non-zero degree are visited
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() > 0 && !visited[i]) {
                return false;
            }
        }

        return true;
    }

    /**
     * Depth First Search algorithm to traverse the graph
     * @param v The current vertex
     * @param visited Array to mark visited vertices
     */
    private void dfs(int v, boolean[] visited) {
        visited[v] = true;

        for (int neighbor : adjacencyList.get(v)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }

    /**
     * Count the number of vertices with odd degree
     * @return The count of vertices with odd degree
     */
    private int countOddDegreeVertices() {
        int count = 0;
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() % 2 != 0) {
                count++;
            }
        }
        return count;
    }

    /**
     * Check if the graph has an Eulerian path or circuit
     * @return 0 for no Eulerian path, 1 for Eulerian path, 2 for Eulerian circuit
     */
    public int hasEulerianPathOrCircuit() {
        // Check if graph is connected
        if (!isConnected()) {
            return 0; // No Eulerian path
        }

        // Count vertices with odd degree
        int oddCount = countOddDegreeVertices();

        if (oddCount == 0) {
            return 2; // Eulerian circuit exists
        } else if (oddCount == 2) {
            return 1; // Eulerian path exists
        } else {
            return 0; // No Eulerian path
        }
    }

    /**
     * Print the degree of each vertex (land mass)
     */
    public void printDegrees() {
        System.out.println("Degrees of vertices (land masses):");
        for (int i = 0; i < vertices; i++) {
            System.out.println("Land mass " + i + ": " + adjacencyList.get(i).size() + " bridges");
        }
    }

    /**
     * Main method to demonstrate the Königsberg Bridge Problem
     */
    public static void main(String[] args) {
        // Create a graph representing the Königsberg Bridge Problem
        // 4 vertices representing the 4 land masses
        KonigsbergBridgeProblem kbp = new KonigsbergBridgeProblem(4);

        // Add the 7 bridges as edges in the graph
        // Land masses are labeled 0, 1, 2, 3
        // Vertex 0: The northern bank
        // Vertex 1: The southern bank
        // Vertex 2: Island A
        // Vertex 3: Island B

        kbp.addEdge(0, 2); // Bridge 1 connecting northern bank to island A
        kbp.addEdge(0, 2); // Bridge 2 connecting northern bank to island A
        kbp.addEdge(0, 3); // Bridge 3 connecting northern bank to island B
        kbp.addEdge(1, 2); // Bridge 4 connecting southern bank to island A
        kbp.addEdge(1, 3); // Bridge 5 connecting southern bank to island B
        kbp.addEdge(1, 3); // Bridge 6 connecting southern bank to island B
        kbp.addEdge(2, 3); // Bridge 7 connecting island A to island B

        // Print the degrees of each land mass
        kbp.printDegrees();

        // Check if an Eulerian path or circuit exists
        int result = kbp.hasEulerianPathOrCircuit();

        System.out.println("\nAnalysis of the Königsberg Bridge Problem:");
        switch (result) {
            case 0:
                System.out.println("As Euler proved in 1736, it is impossible to walk through Königsberg crossing each bridge exactly once.");
                System.out.println("This is because more than two land masses have an odd number of bridges.");
                break;
            case 1:
                System.out.println("An Eulerian path exists, but not an Eulerian circuit.");
                System.out.println("You can cross each bridge exactly once, but you cannot start and end at the same place.");
                break;
            case 2:
                System.out.println("An Eulerian circuit exists. You can cross each bridge exactly once and return to your starting point.");
                break;
        }

        // Create a modified version of the problem to demonstrate a solvable case
        System.out.println("\n--- Modified Königsberg with One Additional Bridge ---");
        KonigsbergBridgeProblem modifiedKbp = new KonigsbergBridgeProblem(4);

        // Add the original 7 bridges
        modifiedKbp.addEdge(0, 2);
        modifiedKbp.addEdge(0, 2);
        modifiedKbp.addEdge(0, 3);
        modifiedKbp.addEdge(1, 2);
        modifiedKbp.addEdge(1, 3);
        modifiedKbp.addEdge(1, 3);
        modifiedKbp.addEdge(2, 3);

        // Add one additional bridge to make it solvable
        modifiedKbp.addEdge(0, 1);

        // Print the degrees of each land mass in the modified problem
        modifiedKbp.printDegrees();

        // Check if an Eulerian path or circuit exists in the modified problem
        int modifiedResult = modifiedKbp.hasEulerianPathOrCircuit();

        System.out.println("\nAnalysis of the Modified Königsberg Bridge Problem:");
        switch (modifiedResult) {
            case 0:
                System.out.println("It is still impossible to walk crossing each bridge exactly once.");
                break;
            case 1:
                System.out.println("With the additional bridge, an Eulerian path now exists!");
                System.out.println("You can cross each bridge exactly once, but you must start and end at different locations.");
                break;
            case 2:
                System.out.println("With the additional bridge, an Eulerian circuit now exists!");
                System.out.println("You can cross each bridge exactly once and return to your starting point.");
                break;
        }
    }
}

Extended Program with Eulerian Path Finding

Here's an enhanced version that not only checks for the existence of an Eulerian path but also finds and prints the path if it exists:

import java.util.*;

/**
 * Enhanced version of the Königsberg Bridge Problem solution that also
 * finds and displays an Eulerian path or circuit if one exists.
 */
public class KonigsbergBridgeProblemWithPath {

    // Number of vertices (land masses) in the graph
    private int vertices;

    // Adjacency list to represent the graph
    private ArrayList<ArrayList<Integer>> adjacencyList;

    // Track the number of edges
    private int edgeCount;

    // Store the names of the land masses for better output
    private String[] landMassNames;

    /**
     * Constructor to initialize the graph with a specified number of vertices
     * @param vertices The number of vertices (land masses)
     */
    public KonigsbergBridgeProblemWithPath(int vertices) {
        this.vertices = vertices;
        this.adjacencyList = new ArrayList<>(vertices);
        this.edgeCount = 0;

        // Initialize the adjacency list for each vertex
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Set default land mass names
        this.landMassNames = new String[vertices];
        for (int i = 0; i < vertices; i++) {
            landMassNames[i] = "Land Mass " + i;
        }
    }

    /**
     * Set custom names for the land masses
     * @param names Array of names for the land masses
     */
    public void setLandMassNames(String[] names) {
        if (names.length == vertices) {
            this.landMassNames = names;
        } else {
            System.out.println("Error: The number of names must match the number of vertices.");
        }
    }

    /**
     * Add an undirected edge (bridge) between two vertices (land masses)
     * @param v First vertex (land mass)
     * @param w Second vertex (land mass)
     */
    public void addEdge(int v, int w) {
        // Add edge from v to w and from w to v (undirected graph)
        adjacencyList.get(v).add(w);
        adjacencyList.get(w).add(v);
        edgeCount++;
    }

    /**
     * Check if the graph is connected
     * This is a required condition for an Eulerian path or circuit
     * @return true if the graph is connected, false otherwise
     */
    private boolean isConnected() {
        // Boolean array to mark visited vertices
        boolean[] visited = new boolean[vertices];

        // Find a vertex with non-zero degree
        int startVertex = 0;
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() > 0) {
                startVertex = i;
                break;
            }
        }

        // Perform DFS starting from the vertex found
        dfs(startVertex, visited);

        // Check if all vertices with non-zero degree are visited
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() > 0 && !visited[i]) {
                return false;
            }
        }

        return true;
    }

    /**
     * Depth First Search algorithm to traverse the graph
     * @param v The current vertex
     * @param visited Array to mark visited vertices
     */
    private void dfs(int v, boolean[] visited) {
        visited[v] = true;

        for (int neighbor : adjacencyList.get(v)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }

    /**
     * Count the number of vertices with odd degree
     * @return The count of vertices with odd degree
     */
    private int countOddDegreeVertices() {
        int count = 0;
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() % 2 != 0) {
                count++;
            }
        }
        return count;
    }

    /**
     * Find a vertex with odd degree, or any vertex with non-zero degree
     * @return The index of the starting vertex for Eulerian path
     */
    private int findStartVertex() {
        // First, try to find a vertex with odd degree (start of Eulerian path)
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() % 2 != 0) {
                return i;
            }
        }

        // If no vertex with odd degree, find any vertex with non-zero degree
        for (int i = 0; i < vertices; i++) {
            if (adjacencyList.get(i).size() > 0) {
                return i;
            }
        }

        return 0; // Default to vertex 0 if no suitable vertex found
    }

    /**
     * Check if the graph has an Eulerian path or circuit
     * @return 0 for no Eulerian path, 1 for Eulerian path, 2 for Eulerian circuit
     */
    public int hasEulerianPathOrCircuit() {
        // Check if graph is connected
        if (!isConnected()) {
            return 0; // No Eulerian path
        }

        // Count vertices with odd degree
        int oddCount = countOddDegreeVertices();

        if (oddCount == 0) {
            return 2; // Eulerian circuit exists
        } else if (oddCount == 2) {
            return 1; // Eulerian path exists
        } else {
            return 0; // No Eulerian path
        }
    }

    /**
     * Print the degree of each vertex (land mass)
     */
    public void printDegrees() {
        System.out.println("Degrees of vertices (land masses):");
        for (int i = 0; i < vertices; i++) {
            System.out.println(landMassNames[i] + ": " + adjacencyList.get(i).size() + " bridges");
        }
    }

    /**
     * Find and print an Eulerian path or circuit
     */
    public void printEulerianPath() {
        int result = hasEulerianPathOrCircuit();

        if (result == 0) {
            System.out.println("No Eulerian path exists in this graph.");
            return;
        }

        // Create a copy of the adjacency list for the algorithm
        ArrayList<ArrayList<Integer>> adjCopy = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjCopy.add(new ArrayList<>(adjacencyList.get(i)));
        }

        // Find a starting vertex
        int startVertex = findStartVertex();

        // Stack for the algorithm and list for the result
        Stack<Integer> stack = new Stack<>();
        List<Integer> path = new ArrayList<>();

        stack.push(startVertex);

        while (!stack.isEmpty()) {
            int current = stack.peek();

            if (adjCopy.get(current).size() > 0) {
                // Get the next neighbor
                int next = adjCopy.get(current).get(0);

                // Remove the edge (both directions)
                adjCopy.get(current).remove(Integer.valueOf(next));
                adjCopy.get(next).remove(Integer.valueOf(current));

                // Push the neighbor to the stack
                stack.push(next);
            } else {
                // No more edges, add to path
                path.add(stack.pop());
            }
        }

        // Reverse the path
        Collections.reverse(path);

        // Check if we've used all edges
        int usedEdges = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            usedEdges++;
        }

        if (usedEdges != edgeCount) {
            System.out.println("Could not find a complete Eulerian path.");
            return;
        }

        // Print the path
        System.out.println("\nEulerian " + (result == 2 ? "Circuit" : "Path") + ":");
        for (int i = 0; i < path.size(); i++) {
            System.out.print(landMassNames[path.get(i)]);
            if (i < path.size() - 1) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }

    /**
     * Main method to demonstrate the Königsberg Bridge Problem
     */
    public static void main(String[] args) {
        // Create a graph representing the Königsberg Bridge Problem
        KonigsbergBridgeProblemWithPath kbp = new KonigsbergBridgeProblemWithPath(4);

        // Set names for the land masses
        String[] names = {"Northern Bank", "Southern Bank", "Island A", "Island B"};
        kbp.setLandMassNames(names);

        // Add the 7 bridges as edges in the graph
        kbp.addEdge(0, 2); // Bridge 1 connecting northern bank to island A
        kbp.addEdge(0, 2); // Bridge 2 connecting northern bank to island A
        kbp.addEdge(0, 3); // Bridge 3 connecting northern bank to island B
        kbp.addEdge(1, 2); // Bridge 4 connecting southern bank to island A
        kbp.addEdge(1, 3); // Bridge 5 connecting southern bank to island B
        kbp.addEdge(1, 3); // Bridge 6 connecting southern bank to island B
        kbp.addEdge(2, 3); // Bridge 7 connecting island A to island B

        // Print the degrees of each land mass
        kbp.printDegrees();

        // Check if an Eulerian path or circuit exists
        int result = kbp.hasEulerianPathOrCircuit();

        System.out.println("\nAnalysis of the Königsberg Bridge Problem:");
        switch (result) {
            case 0:
                System.out.println("As Euler proved in 1736, it is impossible to walk through Königsberg crossing each bridge exactly once.");
                System.out.println("This is because more than two land masses have an odd number of bridges.");
                break;
            case 1:
                System.out.println("An Eulerian path exists, but not an Eulerian circuit.");
                System.out.println("You can cross each bridge exactly once, but you cannot start and end at the same place.");
                kbp.printEulerianPath();
                break;
            case 2:
                System.out.println("An Eulerian circuit exists. You can cross each bridge exactly once and return to your starting point.");
                kbp.printEulerianPath();
                break;
        }

        // Create a modified version of the problem with one additional bridge
        System.out.println("\n--- Modified Königsberg with One Additional Bridge ---");
        KonigsbergBridgeProblemWithPath modifiedKbp = new KonigsbergBridgeProblemWithPath(4);
        modifiedKbp.setLandMassNames(names);

        // Add the original 7 bridges
        modifiedKbp.addEdge(0, 2);
        modifiedKbp.addEdge(0, 2);
        modifiedKbp.addEdge(0, 3);
        modifiedKbp.addEdge(1, 2);
        modifiedKbp.addEdge(1, 3);
        modifiedKbp.addEdge(1, 3);
        modifiedKbp.addEdge(2, 3);

        // Add one additional bridge to make it solvable
        modifiedKbp.addEdge(0, 1);

        // Print the degrees of each land mass in the modified problem
        modifiedKbp.printDegrees();

        // Check if an Eulerian path or circuit exists in the modified problem
        int modifiedResult = modifiedKbp.hasEulerianPathOrCircuit();

        System.out.println("\nAnalysis of the Modified Königsberg Bridge Problem:");
        switch (modifiedResult) {
            case 0:
                System.out.println("It is still impossible to walk crossing each bridge exactly once.");
                break;
            case 1:
                System.out.println("With the additional bridge, an Eulerian path now exists!");
                System.out.println("You can cross each bridge exactly once, but you must start and end at different locations.");
                modifiedKbp.printEulerianPath();
                break;
            case 2:
                System.out.println("With the additional bridge, an Eulerian circuit now exists!");
                System.out.println("You can cross each bridge exactly once and return to your starting point.");
                modifiedKbp.printEulerianPath();
                break;
        }
    }
}

Modern Applications of Euler's Work

The concepts developed by Euler for the Königsberg Bridge Problem have far-reaching applications:

1. Network Design: Planning efficient routes for mail delivery, garbage collection, and transit systems.

2. Circuit Design: Creating electronic circuits that can be properly traced for manufacturing.

3. DNA Sequencing: Assembling genome fragments using Eulerian paths.

4. Algorithm Design: Graph traversal algorithms are foundational to many computer science problems.

5. Operations Research: Optimizing resource allocation and scheduling.

The simple question about seven bridges led to the development of graph theory, which has become a fundamental area of mathematics with countless applications in computer science, engineering, biology, and many other fields.

The Java programs provided demonstrate not only the original problem but also how to create a general solution for determining whether any graph has an Eulerian path or circuit, a concept that continues to be relevant in many modern applications.