Euleriska vägen är en bana i en graf som besöker varje kant exakt en gång. Eulerisk krets är en Eulerisk bana som börjar och slutar på samma vertex.
Hur tar man reda på om en given graf är Eulerisk eller inte?
Problemet är detsamma som följande fråga. Är det möjligt att rita en given graf utan att lyfta pennan från pappret och utan att spåra någon av kanterna mer än en gång.
En graf kallas eulerisk om den har en eulerisk cykel och kallas semi-eulerisk om den har en eulerisk bana. Problemet verkar likna Hamiltonian Path som är NP-komplett problem för en allmän graf. Lyckligtvis kan vi hitta om en given graf har en Eulerisk väg eller inte i polynomtid. Faktum är att vi kan hitta det i O(V+E) tid.
Följande är några intressanta egenskaper hos oriktade grafer med en Eulerisk väg och cykel. Vi kan använda dessa egenskaper för att ta reda på om en graf är Eulerian eller inte.
Euleriska cykeln: En oriktad graf har Eulerisk cykel om följande två villkor är sanna.
- Alla hörn med grader som inte är noll är anslutna. Vi bryr oss inte om hörn med noll grader eftersom de inte tillhör Eulerian Cycle eller Path (vi betraktar bara alla kanter).
- Alla hörn har jämn grad.
Eulerisk väg: En oriktad graf har Eulerian Path om följande två villkor är sanna.
- Samma som villkor (a) för Eulerisk cykel.
- Om noll eller två hörn har udda grad och alla andra hörn har jämn grad. Observera att endast en vertex med udda grad inte är möjlig i en oriktad graf (summan av alla grader är alltid jämn i en oriktad graf)
Observera att en graf utan kanter anses vara Eulerian eftersom det inte finns några kanter att korsa.
Hur fungerar detta?
I Eulerian path, varje gång vi besöker en vertex v, går vi genom två obesökta kanter med en ändpunkt som v. Därför måste alla mellersta hörn i Eulerian Path ha jämn grad. För Eulerisk cykel kan vilken vertex som helst vara mittpunkt, därför måste alla hörn ha jämn grad.
Genomförande:
C++
ändra fil linux
// A C++ program to check if a given graph is Eulerian or not> #include> #include> using> namespace> std;> // A class that represents an undirected graph> class> Graph> {> >int> V;>// No. of vertices> >list<>int>>*adj;>// A dynamic array of adjacency lists> public>:> >// Constructor and destructor> >Graph(>int> V) {>this>->V = V; adj =>new> list<>int>>[I]; }> >~Graph() {>delete> [] adj; }>// To avoid memory leak> >// function to add an edge to graph> >void> addEdge(>int> v,>int> w);> >// Method to check if this graph is Eulerian or not> >int> isEulerian();> >// Method to check if all non-zero degree vertices are connected> >bool> isConnected();> >// Function to do DFS starting from v. Used in isConnected();> >void> DFSUtil(>int> v,>bool> visited[]);> };> void> Graph::addEdge(>int> v,>int> w)> {> >adj[v].push_back(w);> >adj[w].push_back(v);>// Note: the graph is undirected> }> void> Graph::DFSUtil(>int> v,>bool> visited[])> {> >// Mark the current node as visited and print it> >visited[v] =>true>;> >// Recur for all the vertices adjacent to this vertex> >list<>int>>::iterator i;> >for> (i = adj[v].begin(); i != adj[v].end(); ++i)> >if> (!visited[*i])> >DFSUtil(*i, visited);> }> // Method to check if all non-zero degree vertices are connected.> // It mainly does DFS traversal starting from> bool> Graph::isConnected()> {> >// Mark all the vertices as not visited> >bool> visited[V];> >int> i;> >for> (i = 0; i visited[i] = false; // Find a vertex with non-zero degree for (i = 0; i if (adj[i].size() != 0) break; // If there are no edges in the graph, return true if (i == V) return true; // Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); // Check if all non-zero degree vertices are visited for (i = 0; i if (visited[i] == false && adj[i].size()>0) returnera falskt; returnera sant; } /* Funktionen returnerar ett av följande värden 0 --> Om grafen inte är Eulerian 1 --> Om grafen har en Euler-bana (Semi-Eulerian) 2 --> Om grafen har en Euler-krets (Eulerian) */ int Graph::isEulerian() { // Kontrollera om alla hörn som inte är noll grader är anslutna om (isConnected() == false) returnerar 0; // Räkna hörn med udda grad int udda = 0; for (int i = 0; i if (adj[i].size() & 1) udda++; // Om antalet är mer än 2, är grafen inte Eulerisk om (udda> 2) returnerar 0; // Om udda count är 2, då semi-eulerian // Om udda antal är 0, då eulerian // Notera att udda count aldrig kan vara 1 för oriktad graf return (udda) } // Funktion för att köra testfall test(Graph &g) { int res = g.isEulerian( if (res == 0) cout<< 'graph is not Eulerian
'; else if (res == 1) cout << 'graph has a Euler path
'; else cout << 'graph has a Euler cycle
'; } // Driver program to test above function int main() { // Let us create and test graphs shown in above figures Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); test(g1); Graph g2(5); g2.addEdge(1, 0); g2.addEdge(0, 2); g2.addEdge(2, 1); g2.addEdge(0, 3); g2.addEdge(3, 4); g2.addEdge(4, 0); test(g2); Graph g3(5); g3.addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); test(g3); // Let us create a graph with 3 vertices // connected in the form of cycle Graph g4(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); test(g4); // Let us create a graph with all vertices // with zero degree Graph g5(3); test(g5); return 0; }> |
>
>
Java
// A Java program to check if a given graph is Eulerian or not> import> java.io.*;> import> java.util.*;> import> java.util.LinkedList;> // This class represents an undirected graph using adjacency list> // representation> class> Graph> {> >private> int> V;>// No. of vertices> >// Array of lists for Adjacency List Representation> >private> LinkedList adj[];> >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> LinkedList[v];> >for> (>int> i=>0>; i adj[i] = new LinkedList(); } //Function to add an edge into the graph void addEdge(int v, int w) { adj[v].add(w);// Add w to v's list. adj[w].add(v); //The graph is undirected } // A function used by DFS void DFSUtil(int v,boolean visited[]) { // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this vertex Iterator i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil(n, visited); } } // Method to check if all non-zero degree vertices are // connected. It mainly does DFS traversal starting from boolean isConnected() { // Mark all the vertices as not visited boolean visited[] = new boolean[V]; int i; for (i = 0; i visited[i] = false; // Find a vertex with non-zero degree for (i = 0; i if (adj[i].size() != 0) break; // If there are no edges in the graph, return true if (i == V) return true; // Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); // Check if all non-zero degree vertices are visited for (i = 0; i if (visited[i] == false && adj[i].size()>0) returnera falskt; returnera sant; } /* Funktionen returnerar ett av följande värden 0 --> Om grafen inte är Eulerian 1 --> Om grafen har en Euler-bana (Semi-Eulerian) 2 --> Om grafen har en Euler-krets (Eulerian) */ int isEulerian() { // Kontrollera om alla icke-noll graders hörn är anslutna om (isConnected() == false) return 0; // Räkna hörn med udda grad int udda = 0; for (int i = 0; i if (adj[i].size()%2!=0) udda++; // Om antalet är mer än 2, är grafen inte Eulerisk om (udda> 2) returnerar 0; / / Om udda antal är 2, då semi-eulerian är 0, då eulerian // Notera att udda räkning aldrig kan vara 1 för oriktad graf return (udda==2)? Funktion för att köra testfall void test() { int res = isEulerian(); out.println('grafen har en Euler-sökväg'); else System.out.println('grafen har en Euler-cykel' } // Driver-metod public static void main(String args[]) { / / Låt oss skapa och testa grafer som visas i ovanstående figurer. Graph g1.addEdge(1, 0), g1.addEdge(2,1); (0, 3); g1.addEdge(3, 4); addEdge(2, 1) g2.addEdge(3, 4); .addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); g3.test(); // Låt oss skapa en graf med 3 hörn // sammankopplade i form av cykel Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Låt oss skapa en graf med alla hörn // med noll grader Graph g5 = new Graph(3); g5.test(); } } // Denna kod är bidragit av Aakash Hasija> |
>
>
Python3
Ersätt javascript-sträng
# Python program to check if a given graph is Eulerian or not> #Complexity : O(V+E)> from> collections>import> defaultdict> # This class represents a undirected graph using adjacency list representation> class> Graph:> >def> __init__(>self>, vertices):> >self>.V>=> vertices># No. of vertices> >self>.graph>=> defaultdict(>list>)># default dictionary to store graph> ># function to add an edge to graph> >def> addEdge(>self>, u, v):> >self>.graph[u].append(v)> >self>.graph[v].append(u)> ># A function used by isConnected> >def> DFSUtil(>self>, v, visited):> ># Mark the current node as visited> >visited[v]>=> True> ># Recur for all the vertices adjacent to this vertex> >for> i>in> self>.graph[v]:> >if> visited[i]>=>=> False>:> >self>.DFSUtil(i, visited)> >'''Method to check if all non-zero degree vertices are> >connected. It mainly does DFS traversal starting from> >node with non-zero degree'''> >def> isConnected(>self>):> ># Mark all the vertices as not visited> >visited>=> [>False>]>*>(>self>.V)> ># Find a vertex with non-zero degree> >for> i>in> range>(>self>.V):> >if> len>(>self>.graph[i]) !>=> 0>:> >break> ># If there are no edges in the graph, return true> >if> i>=>=> self>.V>->1>:> >return> True> ># Start DFS traversal from a vertex with non-zero degree> >self>.DFSUtil(i, visited)> ># Check if all non-zero degree vertices are visited> >for> i>in> range>(>self>.V):> >if> visited[i]>=>=> False> and> len>(>self>.graph[i])>>0>:> >return> False> >return> True> >'''The function returns one of the following values> >0 -->Om grafen inte är Eulerian> >1 -->Om grafen har en Euler-bana (Semi-Eulerian)> >2 -->Om grafen har en Eulerkrets (Eulerian) '''> >def> isEulerian(>self>):> ># Check if all non-zero degree vertices are connected> >if> self>.isConnected()>=>=> False>:> >return> 0> >else>:> ># Count vertices with odd degree> >odd>=> 0> >for> i>in> range>(>self>.V):> >if> len>(>self>.graph[i])>%> 2> !>=> 0>:> >odd>+>=> 1> >'''If odd count is 2, then semi-eulerian.> >If odd count is 0, then eulerian> >If count is more than 2, then graph is not Eulerian> >Note that odd count can never be 1 for undirected graph'''> >if> odd>=>=> 0>:> >return> 2> >elif> odd>=>=> 2>:> >return> 1> >elif> odd>>2>:> >return> 0> ># Function to run test cases> >def> test(>self>):> >res>=> self>.isEulerian()> >if> res>=>=> 0>:> >print>(>'graph is not Eulerian'>)> >elif> res>=>=> 1>:> >print>(>'graph has a Euler path'>)> >else>:> >print>(>'graph has a Euler cycle'>)> # Let us create and test graphs shown in above figures> g1>=> Graph(>5>)> g1.addEdge(>1>,>0>)> g1.addEdge(>0>,>2>)> g1.addEdge(>2>,>1>)> g1.addEdge(>0>,>3>)> g1.addEdge(>3>,>4>)> g1.test()> g2>=> Graph(>5>)> g2.addEdge(>1>,>0>)> g2.addEdge(>0>,>2>)> g2.addEdge(>2>,>1>)> g2.addEdge(>0>,>3>)> g2.addEdge(>3>,>4>)> g2.addEdge(>4>,>0>)> g2.test()> g3>=> Graph(>5>)> g3.addEdge(>1>,>0>)> g3.addEdge(>0>,>2>)> g3.addEdge(>2>,>1>)> g3.addEdge(>0>,>3>)> g3.addEdge(>3>,>4>)> g3.addEdge(>1>,>3>)> g3.test()> # Let us create a graph with 3 vertices> # connected in the form of cycle> g4>=> Graph(>3>)> g4.addEdge(>0>,>1>)> g4.addEdge(>1>,>2>)> g4.addEdge(>2>,>0>)> g4.test()> # Let us create a graph with all vertices> # with zero degree> g5>=> Graph(>3>)> g5.test()> # This code is contributed by Neelam Yadav> |
>
>
C#
// A C# program to check if a given graph is Eulerian or not> using> System;> using> System.Collections.Generic;> > // This class represents an undirected graph using adjacency list> // representation> public> class> Graph> {> >private> int> V;>// No. of vertices> > >// Array of lists for Adjacency List Representation> >private> List<>int>>[]adj;> > >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> List<>int>>[i];> >for> (>int> i=0; i adj[i] = new List |
>
>
java stack
Javascript
> // A Javascript program to check if a given graph is Eulerian or not> // This class represents an undirected graph using adjacency list> // representation> class Graph> {> >// Constructor> >constructor(v)> >{> >this>.V = v;> >this>.adj =>new> Array(v);> >for> (let i = 0; i this.adj[i] = []; } // Function to add an edge into the graph addEdge(v,w) { this.adj[v].push(w);// Add w to v's list. this.adj[w].push(v); //The graph is undirected } // A function used by DFS DFSUtil(v,visited) { // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this vertex for(let i of this.adj[v]) { let n = i; if (!visited[n]) this.DFSUtil(n, visited); } } // Method to check if all non-zero degree vertices are // connected. It mainly does DFS traversal starting from isConnected() { // Mark all the vertices as not visited let visited = new Array(this.V); let i; for (i = 0; i |
>
>Produktion
graph has a Euler path graph has a Euler cycle graph is not Eulerian graph has a Euler cycle graph has a Euler cycle>
Tidskomplexitet: O(V+E)
Rymdkomplexitet: O(V+E)
Nästa artiklar:
Eulerisk väg och krets för riktade grafer.
Fleurys algoritm för att skriva ut en Eulerisk väg eller krets?