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.
- 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).
- Všechny vrcholy mají sudý stupeň.
Eulerovská cesta: Neorientovaný graf má eulerovskou cestu, pokud jsou splněny následující dvě podmínky.
- Stejná jako podmínka (a) pro Eulerovský cyklus.
- 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ň.
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; }> |
>
celé číslo na řetězec
>
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#
int to char
// 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 |
>
>
narodil se Freddie Mercury
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 |
>
>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?