logo

TechCodeview

Eulerin polku ja piiri suuntaamattomalle graafille

Eulerian polku on graafin polku, joka vierailee jokaisessa reunassa täsmälleen kerran. Eulerian piiri on Eulerin polku, joka alkaa ja päättyy samaan kärkeen.

Euler1



inttostr java

Euler2

Euler3

Kuinka selvittää, onko annettu graafi Eulerian vai ei?



Ongelma on sama kuin seuraavassa kysymyksessä. Onko mahdollista piirtää tietty kaavio nostamatta kynää paperista ja jäljittämättä mitään reunoja useammin kuin kerran.
Graafia kutsutaan Eulerianksi, jos sillä on Eulerin sykli, ja puoli-Eulerin sykliksi, jos sillä on Eulerian polku. Ongelma näyttää samanlaiselta kuin Hamiltonin polku, joka on NP täydellinen ongelma yleiselle graafille. Onneksi voimme selvittää, onko tietyllä graafilla Eulerin polku vai ei polynomiajassa. Itse asiassa voimme löytää sen O(V+E)-ajassa.
Seuraavassa on joitain mielenkiintoisia ominaisuuksia suuntaamattomille kuvaajille, joissa on Eulerin polku ja sykli. Voimme käyttää näitä ominaisuuksia selvittääksemme, onko graafi Euleri vai ei.

Eulerian sykli: Suuntaamattomalla graafilla on Eulerin sykli, jos seuraavat kaksi ehtoa ovat totta.

  1. Kaikki pisteet, joiden aste ei ole nolla, on yhdistetty. Emme välitä nolla-asteisista pisteistä, koska ne eivät kuulu Eulerin sykliin tai polkuun (otamme huomioon vain kaikki reunat).
  2. Kaikilla pisteillä on parillinen aste.

Eulerian polku: Suuntaamattomalla graafilla on Eulerin polku, jos seuraavat kaksi ehtoa ovat totta.



  1. Sama kuin ehto (a) Eulerin syklille.
  2. Jos nollalla tai kahdella pisteellä on pariton aste ja kaikilla muilla pisteillä on parillinen aste. Huomaa, että vain yksi pariton asteinen kärki ei ole mahdollinen suuntaamattomassa graafissa (kaikkien asteiden summa on aina parillinen suuntaamattomassa graafissa)

Huomaa, että graafia, jossa ei ole reunoja, pidetään Eulerianina, koska siinä ei ole kuljettavia reunoja.

Miten tämä toimii?
Eulerin polussa joka kerta kun vierailemme kärjessä v, kävelemme kahden vierailemattoman reunan läpi, joiden yksi päätepiste on v. Siksi kaikilla Eulerin polun keskipisteillä on oltava parillinen aste. Eulerin syklissä mikä tahansa kärkipiste voi olla keskipiste, joten kaikilla pisteillä on oltava parillinen aste.

Suositeltu harjoitus Euler-piiri ja polku Kokeile sitä!

Toteutus:

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>>[SISÄÄ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>>::iteraattori 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) palauttaa epätosi; palauttaa tosi; } /* Funktio palauttaa jonkin seuraavista arvoista 0 --> Jos graafi ei ole Euler 1 --> Jos graafilla on Euler-polku (Semi-Euler) 2 --> Jos graafissa on Euler-piiri (Euler) */ int Graph::isEulerian() { // Tarkista, onko kaikki nollasta poikkeavat pisteet kytketty, jos (isConnected() == false) return 0; // Laske pariton aste int odd = 0; for (int i = 0; i if (adj[i].size() & 1) odd++; // Jos määrä on suurempi kuin 2, graafi ei ole Eulerian if (pariton> 2) palauttaa 0; // Jos pariton count on 2, sitten semi-eulerian // Jos pariton määrä on 0, niin euleri // Huomaa, että pariton määrä ei voi koskaan olla 1 ohjaamattoman graafin palauttamiseksi 1 : 2 testi(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; }> 

>

>

Java

tarkista java-versio linuxissa




// 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) palauttaa epätosi; palauttaa tosi; } /* Funktio palauttaa jonkin seuraavista arvoista 0 --> Jos graafi ei ole Euler 1 --> Jos graafilla on Euler-polku (Semi-Euler) 2 --> Jos graafissa on Euler-piiri (Euler) */ int isEulerian() { // Tarkista, onko kaikki nollasta poikkeavat kärjet kytketty, jos (isConnected() == false) return 0; // Laske pariton aste int odd = 0; for (int i = 0; i if (adj[i].size()%2!=0) odd++; // Jos määrä on suurempi kuin 2, graafi ei ole Eulerian if (pariton> 2) palauttaa 0; / / Jos pariton luku on 2, niin puoli-euleri // Jos pariton luku on 0, niin euleri // Huomaa, että pariton määrä ei voi koskaan olla 1 ohjaamattomalle graafin palautukselle (pariton = 2) } //? Funktio testitapausten suorittamiseksi void test() { int res = isEulerian() System.out.println('graafi ei ole Eulerian'); out.println('kaaviossa on Euler-polku'); else System.out.println('kaaviossa on Euler-sykli') } // Ohjainmenetelmä public static void main(String args[]) { / / Luodaan ja testataan kaavioita, jotka näkyvät yllä olevissa kuvissa. Graph g1 = new Graph(5, 0) g1.addEdge(2, 1); (0, 3) g1.test(5); addEdge(2, 1) 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.test(); // Tehdään graafi, jossa on 3 kärkeä // kytkettynä syklin muodossa Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Tehdään graafi, jossa on kaikki kärjet // nolla-asteella Grafi g5 = new Graph(3); g5.test(); } } // Tämän koodin tarjoaa Aakash Hasija> 

>

>

Python 3

Tietokoneverkot




# 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 -->Jos kuvaaja ei ole Eulerian> >1 -->Jos graafilla on Eulerin polku (puoli-Euler)> >2 -->Jos graafissa on Euler-piiri (Euler-piiri) '''> >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>>[in];> >for> (>int> i=0; i adj[i] = new List (); } //Funktion reunan lisääminen kuvaajaan void addEdge(int v, int w) { adj[v].Add(w);// Lisää w v:n luetteloon. adj[w].Lisää(v); //Kaavio on suuntaamaton } // DFS:n käyttämä funktio void DFSUtil(int v,bool []vieraillut) { // Merkitse nykyinen solmu vierailluksi vierailluksi[v] = true; // Toista kaikille tämän kärjen viereisille pisteille foreach(int i in adj[v]){ int n = i; if (!vieraillut[n]) DFSUtil(n, vierailtu); } } // Menetelmä tarkistaa, ovatko kaikki nollasta poikkeavat kärjet // yhdistetty. Se tekee pääasiassa DFS-läpikulkua alkaen boolista isConnected() { // Merkitse kaikki kärjet ei-vieratuiksi bool []vieraillut = new bool[V]; int i; for (i = 0; kävin[i] = epätosi; // Etsi nollasta poikkeava piste (i = 0; i if (adj[i].Count != 0) break; // Jos on ei reunoja graafissa, palauttaa tosi jos (i == V) palauttaa tosi // Aloita DFS-läpikulku nollasta poikkeavasta DFSUtil(i, vierailtu) // Tarkista, onko kaikki nollasta poikkeavat pisteet käyty for (i = 0; i if (vieraillut[i] == false && adj[i].Count> 0) return false; return true; } /* Funktio palauttaa yhden seuraavista arvoista 0 --> Jos kaavio on ei Eulerian 1 --> Jos graafilla on Euler-polku (Semi-Eulerian) 2 --> Jos graafissa on Euler-piiri (Eulerian) */ int isEulerian() { // Tarkista, ovatko kaikki nollasta poikkeavat kärjet kytketty, jos (isConnected() == false) return 0 // Laske pariton aste int odd = 0 for (int i = 0; i if (adj[i].Count%2!=0) odd++; // If; count on suurempi kuin 2, niin graafi ei ole Eulerian, jos (pariton> 2) palauttaa 0 // Jos pariton luku on 2, niin puoli-euleri // Jos pariton luku on 0, niin euleri // Huomaa, että pariton määrä voi ei koskaan saa olla 1 suuntaamattomalle graafin palautukselle (pariton ==2)? 1:2; } // Toiminto testitapausten suorittamiseksi void test() { int res = isEulerian(); if (res == 0) Console.WriteLine('kaavio ei ole Eulerian'); else if (res == 1) Console.WriteLine('kaaviossa on Euler-polku'); else Console.WriteLine('kaaviossa on Eulerin sykli'); } // Ohjainmenetelmä public static void Main(String []args) { // Luodaan ja testataan yllä olevissa kuvissa esitetyt graafit 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(); Kaavio g2 = uusi kuvaaja(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(); Kaavio g3 = uusi kuvaaja(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(); // Tehdään graafi, jossa on 3 kärkeä // kytkettynä syklin muodossa Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Tehdään graafi, jossa on kaikki kärjet // nolla-asteella Grafi g5 = new Graph(3); g5.test(); } } // Tämän koodin on toimittanut PrinciRaj1992>> 

> 
merkkijonojen tasa-arvo javassa

    
   
 
     
  
 
    
 
     
     
    
 
 
  
  > // 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) palauttaa epätosi;    palauttaa tosi;  } /* Funktio palauttaa jonkin seuraavista arvoista 0 --> Jos graafi ei ole Euler 1 --> Jos graafilla on Euler-polku (Semi-Euler) 2 --> Jos graafissa on Euler-piiri (Euler) */ isEulerian() { // Tarkista, ovatko kaikki nollasta poikkeavat kärjet kytketty, jos (this.isConnected() == false) palauttaa 0;    // Laske parittomat pisteet, anna pariton = 0;  for (olkoon i = 0; i2) palauttaa 0;    // Jos pariton luku on 2, niin puoli-euleri.  // Jos pariton luku on 0, niin eulerilainen // Huomaa, että pariton määrä ei voi koskaan olla 1 ohjaamattomalle graafin palautukselle (pariton==2)? 1:2;  } // Toiminto testitapausten suorittamiseksi test() { let res = this.isEulerian();  if (res == 0) document.write('kaavio ei ole Eulerin ');  else if (res == 1) document.write('kaaviossa on Eulerin polku ');  else document.write('kaaviossa on Eulerin sykli ');  } } // Ohjainmenetelmä // Luodaan ja testataan yllä olevissa kuvissa esitetyt graafit. Olkoon 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(); olkoon g2 = uusi Kuvaaja(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(); olkoon g3 = uusi Kuvaaja(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(); // Tehdään graafi, jossa on 3 kärkeä // kytkettynä syklin muodossa. Olkoon g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // Tehdään graafi, jossa on kaikki kärjet // nollaasteella olkoon g5 = new Graph(3); g5.test(); // Tämän koodin tarjoaa avanitrachhadiya2155>> 
  
 
esimerkki java-koodista

    
 
> 
    
 graph has a Euler path graph has a Euler cycle graph is not Eulerian graph has a Euler cycle graph has a Euler cycle>
 
  Aika monimutkaisuus: O(V+E)  
 
  Tilan monimutkaisuus: O(V+E)  
 
  Seuraavat artikkelit:   
Eulerian polku ja piiri ohjattua kuvaajaa varten. 
Fleuryn algoritmi Eulerian polun tai piirin tulostamiseen?