Cammino Euleriano è un percorso in un grafico che visita ogni arco esattamente una volta. Il Circuito Euleriano è un Cammino Euleriano che inizia e finisce sullo stesso vertice.
Come scoprire se un dato grafico è euleriano o no?
Il problema è lo stesso della domanda seguente. È possibile disegnare un dato grafico senza staccare la matita dal foglio e senza tracciare nessuno dei bordi più di una volta.
Un grafo si dice Euleriano se ha un Ciclo Euleriano e si dice Semi-Euleriano se ha un Cammino Euleriano. Il problema sembra simile al Cammino Hamiltoniano che è un problema NP completo per un grafo generale. Fortunatamente, possiamo scoprire se un dato grafo ha o meno un cammino euleriano in tempo polinomiale. Infatti lo troviamo nel tempo O(V+E).
Di seguito sono riportate alcune proprietà interessanti dei grafi non orientati con percorso e ciclo euleriano. Possiamo usare queste proprietà per scoprire se un grafico è euleriano o meno.
system.out.println
Ciclo Euleriano: Un grafo non orientato ha ciclo Euleriano se sono vere le seguenti due condizioni.
- Tutti i vertici con grado diverso da zero sono collegati. Non ci interessano i vertici con grado zero perché non appartengono al ciclo o al percorso euleriano (consideriamo solo tutti i bordi).
- Tutti i vertici hanno grado pari.
Cammino Euleriano: Un grafo non orientato ha cammino euleriano se sono vere le seguenti due condizioni.
- Uguale alla condizione (a) per il ciclo euleriano.
- Se zero o due vertici hanno grado dispari e tutti gli altri vertici hanno grado pari. Si noti che in un grafo non orientato non è possibile avere un solo vertice di grado dispari (in un grafo non orientato la somma di tutti i gradi è sempre pari)
Si noti che un grafo senza spigoli è considerato euleriano perché non ci sono spigoli da attraversare.
Come funziona?
Nel cammino euleriano, ogni volta che visitiamo un vertice v, camminiamo attraverso due bordi non visitati con un punto finale come v. Pertanto, tutti i vertici medi nel cammino euleriano devono avere grado pari. Per il ciclo euleriano, qualsiasi vertice può essere vertice medio, quindi tutti i vertici devono avere grado pari.
Implementazione:
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>>*agg;>// A dynamic array of adjacency lists> public>:> >// Constructor and destructor> >Graph(>int> V) {>this>->V = V; agg =>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>>::iteratore 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) restituisce falso; restituisce vero; } /* La funzione restituisce uno dei seguenti valori 0 --> Se il grafico non è Euleriano 1 --> Se il grafico ha un cammino di Eulero (Semi-Euleriano) 2 --> Se il grafico ha un circuito di Eulero (Euleriano) */ int Graph::isEulerian() { // Controlla se tutti i vertici di grado diverso da zero sono collegati if (isConnected() == false) return 0; // Conta i vertici con grado dispari int dispari = 0; for (int i = 0; i if (adj[i].size() & 1) dispari++; // Se count è maggiore di 2, allora il grafico non è euleriano if (dispari> 2) restituisce 0; // Se dispari count è 2, quindi semi-euleriano. // Se il conteggio dispari è 0, allora euleriano // Nota che il conteggio dispari non può mai essere 1 per il ritorno del grafico non orientato (dispari)? 1 : 2 } // Funzione per eseguire i casi di test void test(Grafico &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; }> |
>
>
Giava
opacità della transizione css
// 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) restituisce falso; restituisce vero; } /* La funzione restituisce uno dei seguenti valori 0 --> Se il grafico non è Euleriano 1 --> Se il grafico ha un cammino di Eulero (Semi-Euleriano) 2 --> Se il grafico ha un circuito di Eulero (Euleriano) */ int isEulerian() { // Controlla se tutti i vertici di grado diverso da zero sono collegati if (isConnected() == false) return 0; // Conta i vertici con grado dispari int dispari = 0; for (int i = 0; i if (adj[i].size()%2!=0) dispari++; // Se count è maggiore di 2, il grafico non è euleriano if (dispari> 2) return 0; / / Se il conteggio dispari è 2, allora semi-euleriano. // Se il conteggio dispari è 0, allora euleriano // Nota che il conteggio dispari non può mai essere 1 per il rendimento del grafico non orientato (dispari==2)? Funzione per eseguire casi di test void test() { int res = isEulerian(); if (res == 0) System.out.println('il grafico non è Euleriano' else if (res == 1) System. out.println('il grafico ha un percorso di Eulero'); else System.out.println('il grafico ha un ciclo di Eulero' } // Metodo del driver public static void main(String args[]) { / / Creiamo e testiamo i grafici mostrati nelle figure sopra Graph g1 = new Graph(5, g1.addEdge(0, 2); (0, 3); g1.addEdge(3, 4); g1.test(); Grafico g2 = nuovo Graph(5); addEdge(2, 1); g2.addEdge(0, 3); g2.addEdge(3, 4); g2.addEdge(4, 0); .addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); g3.prova(); // Creiamo un grafo con 3 vertici // collegati sotto forma di ciclo Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.prova(); // Creiamo un grafico con tutti i vertici // con zero gradi Graph g5 = new Graph(3); g5.prova(); } } // Questo codice è un contributo di Aakash Hasija> |
>
>
Python3
età del dharmendra
# 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 -->Se il grafico non è euleriano> >1 -->Se il grafico ha un cammino di Eulero (Semi-Euleriano)> >2 -->Se il grafico ha un circuito di Eulero (Euleriano) '''> >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>>[]agg;> > >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> List<>int>>[in];> >for> (>int> i=0; i adj[i] = new List |
>
>
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 |
>
rinominare nella directory Linux
>Produzione
graph has a Euler path graph has a Euler cycle graph is not Eulerian graph has a Euler cycle graph has a Euler cycle>
Complessità temporale: O(V+E)
Complessità spaziale: O(V+E)
Prossimi articoli:
Cammino Euleriano e Circuito per un Grafo Diretto.
Algoritmo di Fleury per stampare un percorso o circuito euleriano?