logo

TechCodeview

Calea și circuitul eulerian pentru graficul nedirecționat

Calea Euleriana este o cale într-un grafic care vizitează fiecare muchie exact o dată. Circuitul eulerian este o cale euleriană care începe și se termină pe același vârf.

Euler1



Euler2

Euler3

Cum să aflați dacă un anumit grafic este eulerian sau nu?



Problema este aceeași cu următoarea întrebare. Este posibil să desenați un anumit grafic fără a ridica creionul de pe hârtie și fără a trasa vreuna din margini de mai multe ori?
Un grafic se numește eulerian dacă are un ciclu eulerian și se numește semi-eulerian dacă are o cale euleriana. Problema pare similară cu calea Hamiltoniană, care este o problemă completă NP pentru un grafic general. Din fericire, putem afla dacă un graf dat are sau nu o cale euleriana în timp polinomial. De fapt, îl putem găsi în timp O(V+E).
Următoarele sunt câteva proprietăți interesante ale graficelor nedirecționate cu o cale și un ciclu eulerian. Putem folosi aceste proprietăți pentru a afla dacă un grafic este eulerian sau nu.

Ciclul Eulerian: Un grafic nedirecționat are ciclu eulerian dacă următoarele două condiții sunt adevărate.

  1. Toate vârfurile cu grad diferit de zero sunt conectate. Nu ne pasă de vârfurile cu grad zero pentru că nu aparțin ciclului sau căii Eulerian (luăm în considerare doar toate muchiile).
  2. Toate vârfurile au grad par.

Calea Euleriana: Un grafic nedirecționat are cale euleriana dacă următoarele două condiții sunt adevărate.



  1. La fel ca și condiția (a) pentru Ciclul Eulerian.
  2. Dacă zero sau două vârfuri au grad impar și toate celelalte vârfuri au grad par. Rețineți că un singur vârf cu grad impar nu este posibil într-un grafic nedirecționat (suma tuturor gradelor este întotdeauna pare într-un grafic nedirecționat)

Rețineți că un grafic fără muchii este considerat eulerian deoarece nu există muchii de parcurs.

Cum funcţionează asta?
În calea Euleriană, de fiecare dată când vizităm un vârf v, trecem prin două muchii nevizitate cu un punct final ca v. Prin urmare, toate vârfurile mijlocii din Calea Euleriană trebuie să aibă un grad par. Pentru Ciclul Eulerian, orice vârf poate fi vârf mijlociu, prin urmare toate vârfurile trebuie să aibă un grad par.

Practică recomandată circuitul Euler și calea Încercați!

Implementare:

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;>>>public>:> >// Constructor and destructor> >Graph(>int> V) {>this>->V = V; adj =>new> list<>int>>[ÎN]; }> >~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>>::iteratorul 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) returnează fals; returnează adevărat; } /* Funcția returnează una dintre următoarele valori 0 --> Dacă graficul nu este eulerian 1 --> Dacă graficul are o cale Euler (semi-euleriană) 2 --> Dacă graficul are un circuit Euler (eulerian) */ int Graph::isEulerian() { // Verificați dacă toate vârfurile de grad diferit de zero sunt conectate dacă (isConnected() == false) returnează 0; // Numără vârfurile cu grad impar int odd = 0; pentru (int i = 0; i if (adj[i].size() & 1) odd++; // Dacă numărul este mai mare de 2, atunci graficul nu este eulerian dacă (impar> 2) returnează 0; // Dacă impar count este 2, atunci semi-eulerian // Dacă numărul impar este 0, atunci eulerian // Rețineți că numărul impar nu poate fi niciodată 1 pentru graf nedirecționat (impar) } // Funcție pentru a rula cazurile de testare 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; }> 

>

hopa concepte 
>

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) returnează fals; returnează adevărat; } /* Funcția returnează una dintre următoarele valori 0 --> Dacă graficul nu este eulerian 1 --> Dacă graficul are o cale Euler (semi-euleriană) 2 --> Dacă graficul are un circuit Euler (eulerian) */ int isEulerian() { // Verificați dacă toate vârfurile de grad diferit de zero sunt conectate dacă (isConnected() == false) returnează 0; // Numără vârfurile cu grad impar int odd = 0; pentru (int i = 0; i dacă (adj[i].size()%2!=0) odd++; // Dacă numărul este mai mare de 2, atunci graficul nu este eulerian dacă (impar> 2) returnează 0; / / Dacă numărul impar este 2, atunci semi-eulerian // Dacă numărul impar este 0, atunci eulerian // Rețineți că numărul impar nu poate fi niciodată 1 pentru un grafic nedirecționat (impar==2) } //; Funcție pentru a rula cazuri de testare void test() { int res = isEulerian(); if (res == 0) System.out.println('graph nu este Eulerian' else if (res == 1) System. out.println('graph are o cale Euler' else System.out.println('graph are un Euler cycle'); } // Metoda driver public static void main(String args[]) { / / Să creăm și să testăm graficele prezentate în figurile de mai sus (0, 3); g1.addEdge(3, 4); Graph g2 (5, 0); addEdge(2, 1); g2.addEdge(3, 4) Graph 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(); // Să creăm un grafic cu 3 vârfuri // conectate sub formă de ciclu Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Să creăm un grafic cu toate vârfurile // cu gradul zero Graph g5 = new Graph(3); g5.test(); } } // Acest cod este contribuit de Aakash Hasija> 

>

>

Python3




inkscape vs gimp
# 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])>>>>:> >return> False> >return> True> >'''The function returns one of the following values> >0 -->Dacă graficul nu este eulerian> >1 -->Dacă graficul are o cale Euler (Semi-Eulerian)> >2 -->Dacă graficul are un circuit Euler (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>>>>:> >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>>[în];> >for> (>int> i=0; i adj[i] = new List (); } //Funcție pentru a adăuga o margine în grafic void addEdge(int v, int w) { adj[v].Add(w);// Adăugați w la lista v. adj[w].Add(v); //Graficul este nedirecționat } // O funcție folosită de DFS void DFSUtil(int v,bool []visited) { // Marcați nodul curent ca vizitat vizitat[v] = true; // Recură pentru toate vârfurile adiacente acestui vârf foreach(int i în adj[v]){ int n = i; if (!vizited[n]) DFSUtil(n, vizitat); } } // Metodă pentru a verifica dacă toate vârfurile de grad diferit de zero sunt // conectate. În principal face traversarea DFS pornind de la bool isConnected() { // Marchează toate nodurile ca nevizitate bool []visited = new bool[V]; int i; pentru (i = 0; am vizitat[i] = fals; // Găsiți un vârf cu grad diferit de zero pentru (i = 0; i dacă (adj[i).Număr != 0) pauză; // Dacă există fără margini în grafic, returnează adevărat dacă (i == V) returnează adevărat // Începe traversarea DFS de la un vârf cu DFSUtil(i, vizitat) // Verificați dacă sunt vizitate toate vârfurile de grad diferit de zero; for (i = 0; i if (vizited[i] == false && adj[i].Count> 0) return false; return true; } /* Funcția returnează una dintre următoarele valori 0 --> Dacă graficul este not Euler 1 --> Dacă graficul are o cale Euler (Semi-Eulerian) 2 --> Dacă graficul are un Euler Circuit (Eulerian) */ int isEulerian() { // Verificați dacă toate vârfurile de grad diferit de zero sunt conectate dacă (isConnected() == false) returnează 0 // Numără vârfurile cu grad impar int odd = 0 pentru (int i = 0; i if (adj[i).Count%2!=0) odd++; // If count este mai mare de 2, atunci graficul nu este eulerian dacă (impar> 2) returnează 0 // Dacă numărul impar este 2, atunci semi-eulerian // Dacă numărul impar este 0, atunci eulerian // Rețineți că numărul impar poate nu fi niciodată 1 pentru returnarea nedirecționată a graficului (impar==2)? 1 : 2; } // Funcție pentru a rula cazuri de testare void test() { int res = isEulerian(); if (res == 0) Console.WriteLine('graful nu este eulerian'); else if (res == 1) Console.WriteLine('graful are o cale Euler'); else Console.WriteLine('graful are un ciclu Euler'); } // Metoda driver public static void Main(String []args) { // Să creăm și să testăm grafice prezentate în figurile de mai sus 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(); Grafic g2 = grafic nou(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(); Graficul g3 = grafic nou(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(); // Să creăm un grafic cu 3 vârfuri // conectate sub formă de ciclu Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Să creăm un grafic cu toate vârfurile // cu gradul zero Graph g5 = new Graph(3); g5.test(); } } // Acest cod a contribuit de PrinciRaj1992>> 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  > // 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) returnează fals;    returnează adevărat;  } /* Funcția returnează una dintre următoarele valori 0 --> Dacă graficul nu este eulerian 1 --> Dacă graficul are o cale Euler (semi-euleriană) 2 --> Dacă graficul are un circuit Euler (eulerian) */ isEulerian() { // Verificați dacă toate vârfurile de grad diferit de zero sunt conectate dacă (this.isConnected() == false) returnează 0;    // Numără vârfurile cu grad impar lat impar = 0;  pentru (fie i = 0; i2) returnează 0;    // Dacă numărul impar este 2, atunci semi-eulerian.  // Dacă numărul impar este 0, atunci eulerian // Rețineți că numărul impar nu poate fi niciodată 1 pentru returnarea nedirecționată a graficului (impar==2)? 1 : 2;  } // Funcție pentru a rula cazurile de testare test() { let res = this.isEulerian();  if (res == 0) document.write('graph nu este eulerian ');  else if (res == 1) document.write('graph are o cale Euler ');  else document.write('graful are un ciclu Euler ');  } } // Metoda driverului // Să creăm și să testăm graficele prezentate în figurile de mai sus let 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(); fie 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(); fie 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(); // Să creăm un grafic cu 3 vârfuri // conectate sub formă de ciclu let g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Să creăm un grafic cu toate vârfurile // cu gradul zero fie g5 = new Graph(3); g5.test(); // Acest cod este contribuit de avanitrachhadiya2155> 
  
 
    
 
>
 
    
 
>
 
  Ieșire  
 
graph has a Euler path graph has a Euler cycle graph is not Eulerian graph has a Euler cycle graph has a Euler cycle>
 
  Complexitatea timpului: O(V+E)  
 
  Complexitatea spațiului: O(V+E)  
 
  Articole urmatoare:   
Calea și circuitul eulerian pentru grafice direcționate. 
Algoritmul lui Fleury pentru a imprima o cale sau un circuit eulerian?