Eulerovská cesta je cesta v grafu, která navštíví každou hranu právě jednou. Eulerovský okruh je eulerovská cesta, která začíná a končí ve stejném vrcholu.

Jak zjistit, zda je daný graf eulerovský nebo ne?

Problém je stejný jako v následující otázce. Je možné nakreslit daný graf bez zvednutí tužky z papíru a bez obkreslování některé z hran více než jednou?
Graf se nazývá eulerovský, pokud má eulerovský cyklus, a poloeulerovský, pokud má eulerovskou cestu. Problém se zdá podobný Hamiltonovské cestě, což je NP úplný problém pro obecný graf. Naštěstí můžeme v polynomiálním čase zjistit, zda daný graf má eulerovskou cestu nebo ne. Ve skutečnosti ji můžeme najít v čase O(V+E).
Následuje několik zajímavých vlastností neorientovaných grafů s eulerovskou cestou a cyklem. Tyto vlastnosti můžeme použít ke zjištění, zda je graf eulerovský nebo ne.

Eulerovský cyklus: Neorientovaný graf má eulerovský cyklus, pokud jsou splněny následující dvě podmínky.

1. Všechny vrcholy s nenulovým stupněm jsou spojené. Nestaráme se o vrcholy s nulovým stupněm, protože nepatří do Eulerovského cyklu nebo cesty (uvažujeme pouze všechny hrany).
2. Všechny vrcholy mají sudý stupeň.

Eulerovská cesta: Neorientovaný graf má eulerovskou cestu, pokud jsou splněny následující dvě podmínky.

1. Stejná jako podmínka (a) pro Eulerovský cyklus.
2. Jestliže nula nebo dva vrcholy mají lichý stupeň a všechny ostatní vrcholy mají sudý stupeň. Všimněte si, že v neorientovaném grafu není možný pouze jeden vrchol s lichým stupněm (součet všech stupňů je v neorientovaném grafu vždy sudý)

Všimněte si, že graf bez hran je považován za eulerovský, protože neexistují žádné hrany, které by bylo možné procházet.

Jak to funguje?
V eulerovské cestě pokaždé, když navštívíme vrchol v, procházíme dvěma nenavštívenými hranami s jedním koncovým bodem jako v. Všechny střední vrcholy v eulerovské cestě proto musí mít sudý stupeň. Pro Eulerovský cyklus může být jakýkoli vrchol středním vrcholem, proto musí mít všechny vrcholy sudý stupeň.

Doporučená praxe Eulerův okruh a cesta Vyzkoušejte to!

Implementace:

C++

// 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> >[V]; }> > ~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> >::iterátor 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) návrat false; vrátit true; } /* Funkce vrátí jednu z následujících hodnot 0 --> Pokud graf není eulerovský 1 --> Pokud má graf Eulerovu cestu (semi-eulerovský) 2 --> pokud má graf Eulerův obvod (eulerovský) */ int Graph::isEulerian() { // Kontrola, zda jsou všechny vrcholy nenulového stupně propojeny if (isConnected() == false) return 0; // Počítání vrcholů s lichým stupněm int odd = 0; for (int i = 0; i if (adj[i].size() & 1) odd++; // Pokud je počet větší než 2, pak graf není eulerovský, pokud (liché> 2) vrátí 0; // Pokud je liché počet je 2, potom semi-eulerian // Pokud je lichý počet 0, pak euleriánský // Všimněte si, že lichý počet nemůže být nikdy 1 pro neorientovaný návrat grafu (lichý) } // Funkce pro spuštění testovacích případů void test(Graf &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; }>

Jáva

// 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) návrat false; vrátit true; } /* Funkce vrátí jednu z následujících hodnot 0 --> Pokud graf není eulerovský 1 --> Pokud má graf Eulerovu cestu (semi-eulerovský) 2 --> pokud má graf Eulerův obvod (eulerovský) */ int isEulerian() { // Kontrola, zda jsou všechny vrcholy nenulového stupně propojeny if (isConnected() == false) return 0; // Počítání vrcholů s lichým stupněm int odd = 0; for (int i = 0; i if (adj[i].size()%2!=0) odd++; // Pokud je počet větší než 2, pak graf není eulerovský, pokud (lichá> 2) vrátí 0; / / Pokud je lichý počet 2, pak semi-eulerovský // Pokud je lichý počet 0, pak eulerovský // Všimněte si, že lichý počet nemůže být nikdy 1 pro neorientovaný návrat grafu (lichý==2) } //; Funkce pro spuštění testovacích případů void test() { int res = isEulerian() if (res == 0) System.out.println('graf není eulerovský' else if (res == 1) Systém. out.println('graf má Eulerovu cestu' else System.out.println('graf má Eulerův cyklus' } // Metoda ovladače public static void main(String args[]) { /); / Vytvořme a otestujeme grafy uvedené na obrázcích Graph g1 = new Graph(5); g1.addEdge(0, 2); (0, 3).g1.test(); pridatHranu(2, 1) g2.pridatHranu(3, 4); g2.test(5); .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(); // Vytvořme graf se 3 vrcholy // spojenými ve tvaru cyklu Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Vytvořme graf se všemi vrcholy // s nulovým stupněm Graph g5 = new Graph(3); g5.test(); } } // Tento kód přispěl Aakash Hasija>

Python3

# 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 -->Pokud graf není eulerovský> > 1 -->Pokud má graf Eulerovu cestu (semi-eulerovská)> > 2 -->Pokud má graf Eulerův obvod (eulerovský) '''> > 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> >[v];> > for> (> int> i=0; i adj[i] = new List (); } //Funkce pro přidání hrany do grafu void addEdge(int v, int w) { adj[v].Add(w);// Přidání w do seznamu v. adj[w].Add(v); //Graf je neorientovaný } // Funkce používaná DFS void DFSUtil(int v,bool []navštíveno) { // Označení aktuálního uzlu jako navštívené[v] = true; // Opakuje se pro všechny vrcholy sousedící s tímto vrcholem foreach(int i in adj[v]){ int n = i; if (!navštíveno[n]) DFSUtil(n, navštíveno); } } // Metoda pro kontrolu, zda jsou všechny nenulové vrcholy // propojeny. Provádí hlavně procházení DFS počínaje bool isConnected() { // Označí všechny vrcholy jako nenavštívené bool []navštívené = new bool[V]; int i; for (i = 0; i visit[i] = false; // Najděte vrchol s nenulovým stupněm pro (i = 0; i if (adj[i].Count != 0) break); // Pokud existují v grafu nejsou žádné hrany, return true if (i == V) return true // Spuštění DFS procházení z vrcholu s nenulovým stupněm DFSUtil(i, navštíveno); for (i = 0; i if (navštívené[i] == false && adj[i].Count> 0) return false; return true; } /* Funkce vrátí jednu z následujících hodnot 0 --> If graph is není Eulerovský 1 --> Pokud má graf Eulerovu cestu (semieulerovský) 2 --> Pokud má graf Eulerův obvod (eulerovský) */ int isEulerian() { // Zkontrolujte, zda jsou všechny vrcholy nenulového stupně propojeny, pokud (isConnected() == false) return 0 // Počítat vrcholy s lichým stupněm int odd = 0; for (int i = 0; i if (adj[i].Count%2!=0) odd++; počet je větší než 2, pak graf není eulerovský, jestliže (lichý> 2) return 0 // Pokud je lichý počet 2, pak semi-eulerovský // Pokud je lichý počet 0, pak eulerovský // Všimněte si, že lichý počet může nikdy nebýt 1 pro neorientovaný návrat grafu (lichá==2)? 1:2; } // Funkce pro spuštění testovacích případů void test() { int res = isEulerian(); if (res == 0) Console.WriteLine('graf není eulerovský'); else if (res == 1) Console.WriteLine('graf má Eulerovu cestu'); else Console.WriteLine('graf má Eulerův cyklus'); } // Metoda ovladače public static void Main(String []args) { // Vytvořme a otestujme grafy zobrazené na obrázcích výše Graph g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.test(); Graph g2 = new 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(); Graph g3 = new 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(); // Vytvořme graf se 3 vrcholy // spojenými ve tvaru cyklu Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Vytvořme graf se všemi vrcholy // s nulovým stupněm Graph g5 = new Graph(3); g5.test(); } } // Tento kód přispěl PrinceRaj1992>

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 0) návrat false; vrátit true; } /* Funkce vrátí jednu z následujících hodnot 0 --> Pokud graf není eulerovský 1 --> Pokud má graf Eulerovu cestu (semi-eulerovský) 2 --> pokud má graf Eulerův obvod (eulerovský) */ isEulerian() { // Kontrola, zda jsou všechny nenulové vrcholy propojeny if (this.isConnected() == false) return 0; // Spočítejte vrcholy s lichým stupněm let odd = 0; for (ať i = 0; i 2) návrat 0; // Pokud je lichý počet 2, pak semieulerovský. // Pokud je lichý počet 0, pak eulerovský // Všimněte si, že lichý počet nemůže být nikdy 1 pro neorientovaný návrat grafu (lichý==2)? 1:2; } // Funkce pro spuštění testovacích případů test() { let res = this.isEulerian(); if (res == 0) document.write('graf není eulerovský '); else if (res == 1) document.write('graf má Eulerovu cestu '); else document.write('graf má Eulerův cyklus '); } } // Metoda ovladače // Vytvořme a otestujme grafy zobrazené na obrázcích výše nechť g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.test(); nech g2 = new 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(); nech g3 = new 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(); // Vytvořme graf se 3 vrcholy // spojenými ve tvaru cyklu nechť g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Vytvořme graf se všemi vrcholy // s nulovým stupněm let g5 = new Graph(3); g5.test(); // Tento kód přispěl avanitrachhadiya2155>

Výstup

graph has a Euler path graph has a Euler cycle graph is not Eulerian graph has a Euler cycle graph has a Euler cycle 

Časová složitost: O(V+E)

Prostorová složitost: O(V+E)

Další články:
Eulerovská cesta a okruh pro řízené grafy.
Fleuryho algoritmus pro tisk eulerovské cesty nebo okruhu?