Eulerian Circuit Finder
Eulerian Circuit Finder checks if an undirected graph has an Eulerian circuit (a cycle traversing every edge exactly once) and finds one using Hierholzer’s algorithm. Enter the edge list (e.g., A-B,A-C,B-C,B-D,C-D) to test and visualize the circuit.
Methodology Used in Eulerian Circuit Finder
An Eulerian circuit in an undirected graph \\( G = (V, E) \\) is a cycle that traverses every edge exactly once and returns to the starting vertex. A graph has an Eulerian circuit if it is connected and all vertices have even degrees. Hierholzer’s algorithm is used to find the circuit.
Algorithm Steps (Hierholzer’s):
1. Check if the graph is connected and all vertices have even degrees.
2. Start at any vertex and follow unused edges to form a cycle.
3. If remaining edges exist, start a new cycle from a vertex on the current circuit with unused edges.
4. Merge cycles until all edges are used, forming the Eulerian circuit.
Mathematical Formulation:
\\[ \text{Graph } G = (V, E) \text{ has an Eulerian circuit if:} \\] \\[ \text{1. } \deg(v) \text{ is even for all } v \in V \\] \\[ \text{2. } G \text{ is connected (all vertices reachable)} \\] \\[ \text{Circuit: } v_1 \to v_2 \to \cdots \to v_1 \text{ covering all } e \in E \text{ exactly once} \\]Example Calculation
Sample Input
Edges: \\( A-B, A-C, B-C, B-D, C-D \\)
Step 1: Vertices: \\( \{A, B, C, D\} \\), Degrees: \\( A: 2, B: 3, C: 3, D: 2 \\)
Step 2: Odd degrees at \\( B \\) and \\( C \\), so no Eulerian circuit exists.
Sample Input (Eulerian)
Edges: \\( A-B, A-C, B-C, B-D, C-D, A-D \\)
Step 1: Vertices: \\( \{A, B, C, D\} \\), Degrees: \\( A: 3, B: 3, C: 3, D: 3 \\)
Step 2: All degrees odd, graph connected (via DFS).
Step 3: Circuit (e.g.): \\( A \to B \to C \to D \to A \to C \to B \to D \to A \\)
Result: Eulerian Circuit: \\( (A, B, C, D, A, C, B, D, A) \\)