Eulerio kelias yra kelias grafike, kuris kiekvieną kraštą aplanko tiksliai vieną kartą. Eulerio grandinė yra Eulerio kelias, kuris prasideda ir baigiasi toje pačioje viršūnėje.

Kaip sužinoti, ar duotas grafikas yra Eulerio, ar ne?

Problema tokia pati kaip ir toliau pateiktame klausime. Ar galima nubraižyti duotą grafiką nepakeliant nuo popieriaus pieštuko ir nenubrėžiant nė vienos briaunos daugiau nei vieną kartą.
Grafas vadinamas Eulerio, jei jis turi Eulerio ciklą, ir vadinamas pusiau Eulerio, jei jis turi Eulerio kelią. Problema atrodo panaši į Hamiltono kelią, kuris yra NP visiška bendrojo grafiko problema. Laimei, galime sužinoti, ar tam tikras grafikas turi Eulerio kelią, ar ne daugianario laiku. Tiesą sakant, mes galime jį rasti O(V+E) laiku.
Toliau pateikiamos kelios įdomios neorientuotų grafikų su Eulerio keliu ir ciklu savybės. Šias savybes galime naudoti norėdami sužinoti, ar grafikas yra Eulerio, ar ne.

Eulerio ciklas: Nenukreiptas grafikas turi Eulerio ciklą, jei yra teisingos šios dvi sąlygos.

1. Visos viršūnės, kurių laipsnis skiriasi nuo nulio, yra sujungtos. Mums nerūpi nulinio laipsnio viršūnės, nes jos nepriklauso Eulerio ciklui ar keliui (atsižvelgiame tik į visas briaunas).
2. Visos viršūnės turi lyginį laipsnį.

Eulerio kelias: Nenukreiptas grafikas turi Eulerio kelią, jei yra teisingos šios dvi sąlygos.

1. Ta pati sąlyga (a) Eulerio ciklui.
2. Jei nulis arba dvi viršūnės turi nelyginį laipsnį, o visos kitos viršūnės turi lyginį laipsnį. Atkreipkite dėmesį, kad tik viena viršūnė su nelyginiu laipsniu negalima nukreiptame grafe (nekryptiniame grafe visų laipsnių suma visada yra lygi)

Atkreipkite dėmesį, kad grafikas be briaunų laikomas Eulerio, nes nėra briaunų, kurias būtų galima eiti.

Kaip tai veikia?
Eulerio kelyje kiekvieną kartą, kai aplankome viršūnę v, einame per dvi neaplankytas briaunas, kurių vienas galinis taškas yra v. Todėl visos Eulerio kelio vidurinės viršūnės turi būti lyginio laipsnio. Eulerio ciklo atveju bet kuri viršūnė gali būti vidurinė viršūnė, todėl visos viršūnės turi turėti lygų laipsnį.

Rekomenduojamos praktikos Eulerio grandinė ir kelias Išbandykite!

Įgyvendinimas:

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;>>

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) return false; grįžti tiesa; } /* Funkcija grąžina vieną iš šių reikšmių 0 --> Jei grafikas nėra Eulerio 1 --> Jei grafikas turi Eulerio kelią (pusiau Eulerio) 2 --> Jei grafikas turi Eulerio grandinę (Eulerio) */ int isEulerian() { // Patikrinkite, ar visos ne nulinio laipsnio viršūnės yra sujungtos if (isConnected() == false) return 0; // Skaičiuoti viršūnes su nelyginiu laipsniu int nelyginis = 0; for (int i = 0; i if (adj[i].size()%2!=0) nelyginis++; // Jei skaičius didesnis nei 2, tada grafikas nėra Eulerio if (nelyginis> 2) grąžina 0; / / Jei nelyginis skaičius yra 2, tai pusiau euleris // Jei nelyginis skaičius yra 0, tai eulerio skaičius // Atkreipkite dėmesį, kad nelyginis skaičius niekada negali būti 1, jei grąža yra nelyginė (nelyginis = 2) } // Funkcija paleisti bandomuosius atvejus void test() { int res = isEulerian() if (res == 0) System.out.println('grafas nėra Eulerio' else if (res == 1) System). out.println('grafas turi Eulerio kelią'); else System.out.println('grafas turi Eulerio ciklą' } // Tvarkyklės metodas public static void main(String args[]) { / / Sukurkime ir išbandykime grafikus, pavaizduotus aukščiau pateiktuose paveikslėliuose. Graph(5) (0, 3); g1.testas (g2) addEdge(2, 1); .addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); g3.testas(); // Sukurkime grafą su 3 viršūnėmis // sujungtų ciklo pavidalu Grafas g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.testas(); // Sukurkime grafą su visomis viršūnėmis // su nuliu laipsniu Grafas g5 = new Graph(3); g5.testas(); } } // Šį kodą sukūrė Aakash Hasija>>

>   
 
     
 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # 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 -->Jei grafikas nėra Eulerio>   >  1 -->Jei grafikas turi Eulerio kelią (pusiau Eulerio)>   >  2 -->Jei grafikas turi Eilerio grandinę (Eulerio) '''>   >  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>>>    )>   >  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 ();  } //Funkcija įtraukti kraštą į grafiką void addEdge(int v, int w) { adj[v].Add(w);// Pridėti w į v's sąrašą.  adj[w].Pridėti(v); //Grafas nenukreiptas } // DFS naudojama funkcija void DFSUtil(int v,bool []aplankytas) { // Pažymėti dabartinį mazgą kaip aplankytą aplankytas[v] = true;    // Kartoti visoms viršūnėms, esančioms greta šios viršūnės foreach(int i in adj[v]){ int n = i;  if (!aplankytas[n]) DFSUtil(n, aplankytas);  } } // Metodas patikrinti, ar visos nulinio laipsnio viršūnės yra // sujungtos. Ji daugiausia atlieka DFS perėjimą pradedant nuo bool isConnected() { // Pažymėti visas viršūnes kaip neaplankytas bool []visited = new bool[V];  int i;  for (i = 0; aš aplankiau[i] = false; // Raskite viršūnę su nuliu laipsniu, skirtu (i = 0; i if (adj[i].Count != 0) pertrauka; // Jei yra grafe nėra briaunų, grąžina true if (i == V) return true // Pradėti DFS perėjimą nuo viršūnės su nuliniu laipsniu DFSUtil(i, aplankyta) // Patikrinti, ar aplankytos visos ne nulinio laipsnio viršūnės; for (i = 0; i if (aplankytas[i] == false && adj[i].Count> 0) return false; return true; } /* Funkcija grąžina vieną iš šių reikšmių 0 --> Jei grafikas yra ne Eulerio 1 --> Jei grafikas turi Eulerio kelią (pusiau Eulerio) 2 --> Jei grafas turi Eulerio grandinę (Eulerio) */ int isEulerio() { // Patikrinkite, ar visos nulinio laipsnio viršūnės yra sujungtos, jei (isConnected() == false) return 0 // Skaičiuoti viršūnes su nelyginiu laipsniu int odd = 0 for (int i = 0; i if (adj[i].Count%2!=0) odd++; // If; skaičius yra didesnis nei 2, tada grafikas nėra Eulerio, jei (nelyginis> 2) grąžina 0 // Jei nelyginis skaičius yra 2, tada pusiau Eulerio skaičius // Jei nelyginis skaičius yra 0, tada eulerio skaičius // Atkreipkite dėmesį, kad nelyginis skaičius Niekada neturi būti 1, kai gaunama nenukreipta grafo grąža (nelyginis ==2)? 1:2;  } // Funkcija paleisti bandomuosius atvejus void test() { int res = isEulerian();  if (res == 0) Console.WriteLine('grafas nėra Eulerio');  else if (res == 1) Console.WriteLine('grafas turi Eulerio kelią');  else Console.WriteLine('grafas turi Eulerio ciklą');  } // Tvarkyklės metodas public static void Main(String []args) { // Sukurkime ir išbandykime grafikus, pavaizduotus aukščiau esančiuose paveikslėliuose Grafikas 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.testas();    Grafikas g2 = naujas grafikas(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.testas();    Grafikas g3 = naujas grafikas(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.testas();    // Sukurkime grafą su 3 viršūnėmis // sujungtų ciklo pavidalu Grafas g4 = new Graph(3);  g4.addEdge(0, 1);  g4.addEdge(1, 2);  g4.addEdge(2, 0);  g4.testas();    // Sukurkime grafą su visomis viršūnėmis // su nuliu laipsniu Grafas g5 = new Graph(3);  g5.testas();  } } // Šį kodą pateikė 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) return false;    grįžti tiesa;  } /* Funkcija grąžina vieną iš šių reikšmių 0 --> Jei grafikas nėra Eulerio 1 --> Jei grafikas turi Eulerio kelią (pusiau Eulerio) 2 --> Jei grafikas turi Eulerio grandinę (Eulerio) */ isEulerian() { // Patikrinkite, ar visos ne nulinio laipsnio viršūnės yra sujungtos if (this.isConnected() == false) return 0;    // Skaičiuoti viršūnes su nelyginiu laipsniu tegul nelyginis = 0;  for (tegul i = 0; i 2) grąžinti 0;    // Jei nelyginis skaičius yra 2, tada pusiau Euleris.  // Jei nelyginis skaičius yra 0, tai Eulerio // Atkreipkite dėmesį, kad nelyginis skaičius niekada negali būti 1, kai gaunama netiesioginė grafo grąža (nelyginis==2)? 1:2;  } // Funkcija paleisti bandomuosius atvejus test() { let res = this.isEulerian();  if (res == 0) document.write('grafas nėra Eulerio ');  else if (res == 1) document.write('grafas turi Eulerio kelią ');  else document.write('grafas turi Eulerio ciklą ');  } } // Tvarkyklės metodas // Sukurkime ir išbandykime grafikus, pavaizduotus aukščiau esančiuose paveikslėliuose, tegul 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.testas(); tegul g2 = naujas Grafas(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.testas(); tegul g3 = naujas Grafas(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.testas(); // Sukurkime grafą su 3 viršūnėmis // sujungtų ciklo pavidalu tegul g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.testas(); // Sukurkime grafą su visomis viršūnėmis // su nuliu laipsniu tegul g5 = new Graph(3); g5.testas(); // Šį kodą sukūrė avanitrachhadiya2155>>  
  
  
  
  
 
     
 
  
>   
 
     
 
  
                              
                              

                                 Pavasario MVC pamoka