Eulerian Path and Circuit 🎯

Welcome to an exciting journey through the world of Graph Theory! Today, we're going to explore Eulerian Paths and Circuits – concepts that are essential for solving problems related to network traversal.

What is a Graph? 📝

Before we dive into Eulerian Paths and Circuits, let's quickly refresh our memory about what a graph is. A graph consists of nodes (also known as vertices) and edges that connect these nodes.

markdown

   A --- B
   |     |
   C --- D

In the above example, A, B, C, and D are nodes, while the lines between them are edges.

Eulerian Path and Circuit 💡

An Eulerian Path in a graph is a path that traverses every edge exactly once. If the path also returns to the starting node, it becomes an Eulerian Circuit.

Eulerian Path 💡

A graph containing an Eulerian Path will have the following properties:

The graph is connected (every node is reachable from every other node).
The degree of every vertex (number of edges connected to it) is even.

Here's an example of a graph with an Eulerian Path:

markdown

   A --- B
   |     |
   C --- D
   |     |
   E --- F
   |     |
   G --- H

In this graph, the Eulerian Path could be: A -> B -> C -> D -> E -> F -> G -> H -> A

Eulerian Circuit 💡

A graph containing an Eulerian Circuit will have the following properties:

The graph is connected.
The degree of every vertex is even.

Here's an example of a graph with an Eulerian Circuit:

markdown

   A --- B
   |     |
   C --- D
   |     |
   E --- A
   |     |
   F --- C

In this graph, the Eulerian Circuit could be: A -> B -> C -> D -> E -> A -> F -> C

Finding Eulerian Path and Circuit 💡

To find an Eulerian Path or Circuit, follow these steps:

Start from any node in the graph.
Traverse to an unvisited neighbor, if possible. If not, move to the next unvisited node.
Repeat step 2 until you can't move any further. If you reach a point where you can't move any further but still haven't visited every node, there is no Eulerian Path in the graph.
If you've visited every node and returned to the starting node, you've found an Eulerian Circuit. If not, you've found an Eulerian Path.

Code Examples ✅

Python Example for Eulerian Path

python

def eulerian_path(graph, start_node):
    visited = set()
    path = []

    def dfs(node):
        if node not in visited:
            visited.add(node)
            path.append(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)
                elif neighbor in path:
                    return False

            path.pop()
            return True

    if not dfs(start_node):
        print("There is no Eulerian Path.")
        return

    print("Eulerian Path:", path)

# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D', 'E'],
    'D': ['B', 'C'],
    'E': ['C']
}

eulerian_path(graph, 'A')

Java Example for Eulerian Circuit

java

import java.util.*;

public class EulerianCircuit {
    static class Graph {
        Map<String, List<String>> adjacencyList;

        public Graph(Map<String, List<String>> adjacencyList) {
            this.adjacencyList = adjacencyList;
        }

        void dfs(String node, Set<String> visited, Set<String> stack, Map<String, Integer> degree) {
            if (degree.get(node) == null) {
                degree.put(node, 0);
            }

            degree.put(node, degree.get(node) + 1);
            visited.add(node);
            stack.add(node);

            for (String neighbor : adjacencyList.get(node)) {
                if (!visited.contains(neighbor)) {
                    dfs(neighbor, visited, stack, degree);
                }
            }
        }

        boolean hasEulerianCircuit() {
            Map<String, Integer> degree = new HashMap<>();
            Set<String> visited = new HashSet<>();
            Set<String> stack = new HashSet<>();

            for (String node : adjacencyList.keySet()) {
                dfs(node, visited, stack, degree);
            }

            return visited.size() == stack.size() && degree.entrySet().stream().allMatch(entry -> entry.getValue() % 2 == 0);
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D"));
        graph.put("C", Arrays.asList("A", "D", "E"));
        graph.put("D", Arrays.asList("B", "C"));
        graph.put("E", Arrays.asList("C"));

        Graph g = new Graph(graph);

        if (g.hasEulerianCircuit()) {
            System.out.println("The graph has an Eulerian Circuit.");
        } else {
            System.out.println("The graph has no Eulerian Circuit.");
        }
    }
}

Quiz 💡

Conclusion 🎯

Eulerian Paths and Circuits are powerful concepts in graph theory that help us traverse graphs efficiently. They are essential for solving problems related to network traversal in real-world applications.

Happy coding! 💻