logo

TechCodeview

Camí i circuit eulerià per a gràfics no dirigits

Camí Euleriano és un camí en un gràfic que visita cada aresta exactament una vegada. El circuit eulerià és un camí eulerià que comença i acaba al mateix vèrtex.

Euler 1



Euler 2

Euler 3

string java indexof

Com esbrina si un gràfic donat és eulerià o no?



El problema és el mateix que la següent pregunta. És possible dibuixar un gràfic donat sense aixecar el llapis del paper i sense traçar cap de les vores més d'una vegada?
Un graf s'anomena eulerià si té un cicle eulerià i semi-euleriana si té un camí eulerià. El problema sembla similar al camí hamiltonià que és un problema NP complet per a un gràfic general. Afortunadament, podem esbrinar si un gràfic donat té un camí eulerià o no en temps polinomi. De fet, el podem trobar en temps O(V+E).
A continuació es mostren algunes propietats interessants dels gràfics no dirigits amb un camí i un cicle eulerià. Podem utilitzar aquestes propietats per esbrinar si un gràfic és eulerià o no.

Cicle Euleriano: Un gràfic no dirigit té un cicle eulerià si les dues condicions següents són certes.

  1. Tots els vèrtexs amb grau diferent de zero estan connectats. No ens preocupen els vèrtexs amb grau zero perquè no pertanyen al Cicle o Camí d'Euleria (només considerem totes les arestes).
  2. Tots els vèrtexs tenen grau parell.

Camí Euleriano: Un gràfic no dirigit té un camí eulerià si les dues condicions següents són certes.



  1. Igual que la condició (a) per al cicle eulerià.
  2. Si zero o dos vèrtexs tenen grau senar i tots els altres vèrtexs tenen grau parell. Tingueu en compte que només un vèrtex amb grau senar no és possible en un gràfic no dirigit (la suma de tots els graus és sempre parell en un gràfic no dirigit)

Tingueu en compte que un gràfic sense arestes es considera eulerià perquè no hi ha arestes per recórrer.

Com funciona?
En el camí eulerià, cada vegada que visitem un vèrtex v, passem per dues arestes no visitades amb un punt final com a v. Per tant, tots els vèrtexs mitjans del camí eulerià han de tenir un grau parell. Per al cicle eulerià, qualsevol vèrtex pot ser un vèrtex mitjà, per tant, tots els vèrtexs han de tenir un grau parell.

Pràctica recomanada del circuit i del camí d'Euler Prova-ho!

Implementació:

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>>[IN]; }> >~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>>::iterador 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) retorna fals; retornar veritat; } /* La funció retorna un dels valors següents 0 --> Si el gràfic no és Euler 1 --> Si el gràfic té un camí d'Euler (semi-Euler) 2 --> Si el gràfic té un circuit Euler (Euler) */ int Graph::isEulerian() { // Comprova si tots els vèrtexs de grau diferent de zero estan connectats si (isConnected() == false) retorna 0; // Comptar vèrtexs amb grau senar int senar = 0; for (int i = 0; i if (adj[i].size() & 1) odd++; // Si el nombre és superior a 2, aleshores el gràfic no és eulerià si (senar> 2) retorna 0; // Si senar el recompte és 2, llavors semi-euler // Si el recompte imparell és 0, llavors el nombre imparell no pot ser mai 1 per a un retorn de gràfics no dirigit } // Funció per executar casos de prova prova(Gràfic &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




actualitzar en sql amb join

// 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) retorna fals; retornar veritat; } /* La funció retorna un dels valors següents 0 --> Si el gràfic no és Euler 1 --> Si el gràfic té un camí d'Euler (semi-Euler) 2 --> Si el gràfic té un circuit Euler (Euler) */ int isEulerian() { // Comprova si tots els vèrtexs de grau diferent de zero estan connectats si (isConnected() == false) retorna 0; // Comptar vèrtexs amb grau senar int senar = 0; per (int i = 0; i si (adj[i].size()%2!=0) odd++; // Si el nombre és més de 2, aleshores el gràfic no és eulerià si (senar> 2) retorna 0; / / Si el nombre senar és 2, llavors semi-euleriana // Si el nombre imparell és 0, llavors euleriana // Tingueu en compte que el nombre imparell mai pot ser 1 per a un retorn de gràfics no dirigit (impar==2) } //; Funció per executar casos de prova void test() { int res = isEulerian(); out.println('graph té una ruta d'Euler'); else System.out.println('graph té un cicle d'Euler' } // Mètode del controlador public static void main(String args[]) { / / Anem a crear i provar els gràfics que es mostren a les figures anteriors. Graph g1 = new Graph(5) (0, 3); g1.addEdge(3, 4); Graph g2 (g2.addEdge(0,2); addEdge (2, 1); g2.addEdge (0, 3); g2.addEdge (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(); // Creem un gràfic amb 3 vèrtexs // connectats en forma de cicle Gràfic g4 = nou Gràfic(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Creem un gràfic amb tots els vèrtexs // amb grau zero Gràfic g5 = nou Gràfic(3); g5.test(); } } // Aquest codi és aportat per Aakash Hasija> 

>

>

Python 3

lògica proposicional




# 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 -->Si la gràfica no és euleriana> >1 -->Si el gràfic té un camí d'Euler (semi-euleriano)> >2 -->Si el gràfic té un circuit d'Euler (Euler) '''> >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#

q2 mesos




// 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>>[a];> >for> (>int> i=0; i adj[i] = new List (); } //Funció per afegir una vora al gràfic void addEdge(int v, int w) { adj[v].Add(w);// Afegeix w a la llista de v. adj[w].Afegir(v); //El gràfic no està dirigit } // Una funció utilitzada per DFS void DFSUtil(int v,bool []visited) { // Marca el node actual com a visitat visitat[v] = true; // Es repeteix per a tots els vèrtexs adjacents a aquest vèrtex foreach(int i in adj[v]){ int n = i; if (!visitat[n]) DFSUtil(n, visitat); } } // Mètode per comprovar si tots els vèrtexs diferents de zero // estan connectats. Principalment fa un recorregut DFS a partir de bool isConnected() { // Marca tots els vèrtexs com a no visitats bool []visited = new bool[V]; int i; per (i = 0; he visitat[i] = fals; // Troba un vèrtex amb un grau diferent de zero per a (i = 0; i si (adj[i].Compte != 0) trenca; // Si hi ha sense arestes al gràfic, retorna true si (i == V) retorna vertader // Inicia la travessa DFS des d'un vèrtex amb DFSUtil de grau diferent de zero // Comprova si es visiten tots els vèrtexs de grau diferent de zero; for (i = 0; i if (visited[i] == false && adj[i].Count> 0) return false; return true; } /* La funció retorna un dels valors següents 0 --> Si el gràfic és not Euler 1 --> Si el graf té un camí d'Euler (semi-Euler) 2 --> Si el graf té un circuit d'Euler (Euler) */ int isEulerian() { // Comprova si tots els vèrtexs de grau diferent de zero estan connectats si (isConnected() == false) retorna 0 // Compta els vèrtexs amb grau imparell = 0 per (int i = 0; i si (adj[i].Count%2!=0) odd++; // Si el nombre és més de 2, aleshores el gràfic no és eulerià si (senir> 2) retorna 0 // Si el nombre senar és 2, llavors el nombre imparell és 0, llavors el nombre imparell pot mai serà 1 per a un retorn de gràfic no dirigit (senar==2)? 1: 2; } // Funció per executar casos de prova void test() { int res = isEulerian(); if (res == 0) Console.WriteLine('graph no is Eulerian'); else if (res == 1) Console.WriteLine('graph té un camí d'Euler'); else Console.WriteLine('graph té un cicle d'Euler'); } // Mètode del controlador public static void Main(String []args) { // Creem i provem els gràfics mostrats a les figures anteriors Gràfic 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(); Gràfic g2 = nou Gràfic(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(); Gràfic g3 = nou Gràfic(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(); // Creem un gràfic amb 3 vèrtexs // connectats en forma de cicle Gràfic g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Creem un gràfic amb tots els vèrtexs // amb grau zero Gràfic g5 = nou Gràfic(3); g5.test(); } } // Aquest codi aportat per 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) retorna fals;    retornar veritat;  } /* La funció retorna un dels valors següents 0 --> Si el gràfic no és Euler 1 --> Si el gràfic té un camí d'Euler (semi-Euler) 2 --> Si el gràfic té un circuit Euler (Euler) */ isEulerian() { // Comprova si tots els vèrtexs de grau diferent de zero estan connectats si (this.isConnected() == false) retorna 0;    // Comptar vèrtexs amb grau senar deixa senar = 0;  per (sigui i = 0; i2) retorna 0;    // Si el nombre senar és 2, llavors semi-euleriana.  // Si el nombre senar és 0, aleshores euleriana // Tingueu en compte que el nombre senar no pot ser mai 1 per a un retorn de gràfic no dirigit (senar==2)? 1 : 2;  } // Funció per executar casos de prova test() { let res = this.isEulerian();  if (res == 0) document.write('graph no és eulerià ');  sinó si (res == 1) document.write('graph té un camí d'Euler ');  else document.write('graph té un cicle d'Euler ');  } } // Mètode del controlador // Creem i provem els gràfics que es mostren a les figures anteriors 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(); sigui 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(); sigui 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(); // Creem un gràfic amb 3 vèrtexs // connectats en forma de cicle let g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Anem a crear un gràfic amb tots els vèrtexs // amb grau zero let g5 = new Graph(3); g5.test(); // Aquest codi és aportat per avanitrachhadiya2155> 
  
 
    
 
>
 
    
Python imprimeix amb 2 decimals

 
>
 
  Sortida  
 
graph has a Euler path graph has a Euler cycle graph is not Eulerian graph has a Euler cycle graph has a Euler cycle>
 
  Complexitat temporal: O(V+E)  
 
  Complexitat espacial: O(V+E)  
 
  Articles següents:   
Camí i circuit eulerià per a gràfics dirigits. 
L'algoritme de Fleury per imprimir un camí o circuit eulerià?