logo

TechCodeview

무방향 그래프의 오일러 경로 및 회로

오일러 경로 모든 가장자리를 정확히 한 번만 방문하는 그래프의 경로입니다. 오일러 회로는 동일한 꼭지점에서 시작하고 끝나는 오일러 경로입니다.

오일러1



오일러2

오일러3

주어진 그래프가 오일러 ​​그래프인지 아닌지 어떻게 알 수 있나요?



문제는 다음 질문과 같습니다. 종이에서 연필을 떼지 않고 가장자리를 두 번 이상 추적하지 않고 주어진 그래프를 그리는 것이 가능합니까?
그래프에 오일러 순환이 있으면 오일러 그래프라고 하고, 오일러 경로가 있으면 세미 오일러 그래프라고 합니다. 이 문제는 일반 그래프에 대한 NP 완전 문제인 해밀턴 경로(Hamiltonian Path)와 유사해 보입니다. 다행스럽게도 주어진 그래프에 오일러 경로가 있는지 여부는 다항식 시간으로 확인할 수 있습니다. 실제로 O(V+E) 시간 안에 찾을 수 있습니다.
다음은 오일러 경로와 순환을 사용하는 무방향 그래프의 몇 가지 흥미로운 속성입니다. 이러한 속성을 사용하여 그래프가 오일러식인지 여부를 확인할 수 있습니다.

오일러 순환: 무방향 그래프는 다음 두 조건이 참일 경우 오일러 순환을 갖습니다.

  1. 0이 아닌 모든 정점은 연결됩니다. 0차 정점은 오일러 순환이나 경로에 속하지 않기 때문에 신경 쓰지 않습니다(모든 가장자리만 고려합니다).
  2. 모든 정점은 짝수 차수를 가집니다.

오일러 경로: 무방향 그래프는 다음 두 가지 조건이 참일 경우 오일러 경로를 갖습니다.



  1. 오일러 순환의 조건 (a)와 동일합니다.
  2. 0개 또는 2개의 정점이 홀수 차수를 갖고 다른 모든 정점은 짝수 차수를 갖는 경우입니다. 무방향 그래프에서는 홀수 차수를 갖는 하나의 꼭지점만 가능하지 않습니다(무방향 그래프에서는 모든 차수의 합이 항상 짝수임).

간선이 없는 그래프는 횡단할 간선이 없기 때문에 오일러 그래프로 간주됩니다.

어떻게 작동하나요?
오일러 경로에서는 정점 v를 방문할 때마다 한 끝점이 v인 두 개의 방문하지 않은 가장자리를 통과합니다. 따라서 오일러 경로의 모든 중간 정점은 짝수 차수를 가져야 합니다. 오일러 순환의 경우 모든 정점은 중간 정점이 될 수 있으므로 모든 정점은 짝수 차수를 가져야 합니다.

추천 연습 오일러 회로와 경로 실습해 보세요!

구현:

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>>*조정;>// A dynamic array of adjacency lists> public>:> >// Constructor and destructor> >Graph(>int> V) {>this>->V = V; 형용사 =>new> list<>int>>[안에]; }> >~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>>::반복자 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) 거짓을 반환합니다. 사실을 반환; } /* 함수는 다음 값 중 하나를 반환합니다. 0 --> 그래프가 오일러리안이 아닌 경우 1 --> 그래프에 오일러 경로(세미 오일러)가 있는 경우 2 --> 그래프에 오일러 회로(Eulerian)가 있는 경우 */ int Graph::isEulerian() { // 0도가 아닌 모든 정점이 연결되어 있는지 확인합니다. if (isConnected() == false) return 0; // 홀수차 꼭지점 개수 int 홀수 = 0; for (int i = 0; i if (adj[i].size() & 1) 홀수++; // 개수가 2보다 크면 그래프는 오일러식이 아닙니다. if (odd> 2) return 0; // 홀수인 경우 개수는 2이고 세미 오일러리안입니다. // 홀수 개수는 0입니다. // 무방향 그래프의 경우 홀수 개수는 1이 될 수 없습니다. return(odd) 1 : 2 } // 테스트 사례를 실행하는 함수 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; }>

파완딥 라잔 

>

>

자바




// 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) 거짓을 반환합니다. 사실을 반환; } /* 함수는 다음 값 중 하나를 반환합니다. 0 --> 그래프가 오일러리안이 아닌 경우 1 --> 그래프에 오일러 경로(세미 오일러)가 있는 경우 2 --> 그래프에 오일러 회로(Eulerian)가 있는 경우 */ int isEulerian() { // 0도가 아닌 모든 정점이 연결되어 있는지 확인합니다. if (isConnected() == false) return 0; // 홀수차 꼭지점 개수 int 홀수 = 0; for (int i = 0; i if (adj[i].size()%2!=0) 홀수++; // 개수가 2보다 크면 그래프는 오일러식이 아닙니다. if (odd> 2) return 0; / / 홀수가 2이면 세미 오일러입니다. // 홀수가 0이면 오일러입니다. // 방향이 지정되지 않은 그래프 반환의 경우 홀수는 1이 될 수 없습니다(홀수==2)? } // 테스트 케이스를 실행하는 함수 void test() { int res = isEulerian(); if (res == 0) System.out.println('graph는 Eulerian이 아닙니다') else if (res == 1) System. out.println('그래프에 오일러 경로가 있음'); else System.out.println('그래프에 오일러 주기가 있음') } // 드라이버 메서드 public static void main(String args[]) { / / 위 그림과 같은 그래프를 만들고 테스트해 보겠습니다. Graph g1 = new Graph(5) g1.addEdge(0, 2); (0, 3); g1.addEdge(3, 4); 그래프 g2 = new Graph(5); g2.addEdge(0, 2); addEdge(2, 1); g2.addEdge(3, 4); g2.test(); .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(); // 3개의 꼭지점을 갖는 그래프를 생성해 보겠습니다. // 순환 형태로 연결됩니다. Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // 모든 정점이 0도인 그래프를 만들어 보겠습니다. Graph g5 = new Graph(3); g5.test(); } } // 이 코드는 Aakash Hasija가 제공한 것입니다.>

모니터가 뭐야? 

>

>

파이썬3




# 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 -->그래프가 오일러식이 아닌 경우> >1 -->그래프에 오일러 경로가 있는 경우(세미 오일러)> >2 -->그래프에 오일러 회로(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>>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> 

>

>

씨#




// 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>>[]조정;> > >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> List<>int>>[in];> >for> (>int> i=0; i adj[i] = new List (); } //그래프에 간선을 추가하는 함수 void addEdge(int v, int w) { adj[v].Add(w);// v의 목록에 w를 추가합니다. 조정[w].Add(v); //그래프는 방향이 없습니다. } // DFS에서 사용하는 함수 void DFSUtil(int v,bool []visited) { // 현재 노드를 방문한 것으로 표시 Visited[v] = true; // 이 정점에 인접한 모든 정점에 대해 반복됩니다. foreach(int i in adj[v]){ int n = i; if (!visited[n]) DFSUtil(n, 방문함); } } // 0도가 아닌 모든 정점이 // 연결되어 있는지 확인하는 메서드입니다. 주로 bool isConnected() { // 모든 정점을 방문하지 않은 것으로 표시 bool []visited = new bool[V]; 나는 int; for (i = 0; 나는 방문했습니다[i] = false; // 0이 아닌 정점을 찾습니다. for (i = 0; i if (adj[i].Count != 0) break; // 있는 경우 그래프에 간선이 없으면 true를 반환합니다. return true; // 0도가 아닌 정점에서 DFS 순회를 시작합니다. DFSUtil(i, Visited) // 0도가 아닌 모든 정점을 방문했는지 확인합니다. for (i = 0; i if (visited[i] == false && adj[i].Count> 0) return false; return true; } /* 함수는 다음 값 중 하나를 반환합니다. 0 --> 그래프가 다음과 같은 경우 오일러가 아님 1 --> 그래프에 오일러 경로가 있는 경우(세미 오일러) 2 --> 그래프에 오일러 회로가 있는 경우(Eulerian) */ int isEulerian() { // 0도가 아닌 모든 정점이 연결되어 있는지 확인 if (isConnected() == false) return 0; // 홀수 차수를 갖는 정점 개수 int 홀수 = 0 for (int i = 0; i if (adj[i].Count%2!=0) 홀수++; // If 개수가 2보다 크면 그래프는 오일러식이 아닙니다. if (odd> 2) return 0; // 홀수 개수가 2이면 세미 오일러식입니다. // 홀수 개수가 0이면 오일러식입니다. // 홀수 개수는 다음과 같습니다. 방향이 지정되지 않은 그래프 반환에 대해 1이 될 수 없습니다(홀수==2)? 1:2; } // 테스트 케이스를 실행하는 함수 void test() { int res = isEulerian(); if (res == 0) Console.WriteLine('그래프가 오일러리안이 아닙니다'); else if (res == 1) Console.WriteLine('그래프에는 오일러 경로가 있습니다'); else Console.WriteLine('그래프에는 오일러 사이클이 있습니다'); } // 드라이버 메소드 public static void Main(String []args) { // 위 그림과 같은 그래프를 생성하고 테스트해 보겠습니다. 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.테스트(); 그래프 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(); 그래프 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); g3.test(); // 3개의 꼭지점을 갖는 그래프를 생성해 보겠습니다. // 순환 형태로 연결됩니다. Graph g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // 모든 정점이 0도인 그래프를 만들어 보겠습니다. Graph g5 = new Graph(3); g5.test(); } } // PrinciRaj1992가 제공한 이 코드> 

>

>

안드로이드 프로세스 acore가 계속 중지됩니다.

자바스크립트




> // 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) 거짓을 반환합니다. 사실을 반환; } /* 함수는 다음 값 중 하나를 반환합니다. 0 --> 그래프가 오일러리안이 아닌 경우 1 --> 그래프에 오일러 경로(세미 오일러)가 있는 경우 2 --> 그래프에 오일러 회로(Eulerian)가 있는 경우 */ isEulerian() { // 0도가 아닌 모든 정점이 연결되어 있는지 확인합니다. if (this.isConnected() == false) return 0; // 홀수 차수를 갖는 정점 개수를 계산합니다. 홀수 = 0; for (나는 = 0이라고 하자; 나는2) 0을 반환합니다. // 홀수 개수가 2이면 세미 오일러입니다. // 홀수 개수가 0이면 오일러리언입니다. // 무방향 그래프 반환(홀수==2)의 경우 홀수 개수는 1이 될 수 없습니다. 1:2; } // 테스트 케이스를 실행하는 함수 test() { let res = this.isEulerian(); if (res == 0) document.write('그래프는 오일러리안이 아닙니다 '); else if (res == 1) document.write('그래프에는 오일러 경로가 있습니다 '); else document.write('그래프에는 오일러 사이클이 있습니다 '); } } // 드라이버 메소드 // 위 그림과 같은 그래프를 생성하고 테스트해 보겠습니다. 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.테스트(); 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(); 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(); // 3개의 꼭지점을 갖는 그래프를 생성합니다. // 순환 형태로 연결되어 있습니다. let g4 = new Graph(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); g4.test(); // 모든 정점이 0차인 // 그래프를 생성해 보겠습니다. let g5 = new Graph(3); g5.test(); // 이 코드는 avanitrachhadiya2155가 제공한 것입니다.> 

>

>

산출 

graph has a Euler path graph has a Euler cycle graph is not Eulerian graph has a Euler cycle graph has a Euler cycle>

시간 복잡도: O(V+E)

공간 복잡도: O(V+E)

다음 기사:
유향 그래프의 오일러 경로 및 회로.
오일러 경로 또는 회로를 인쇄하는 Fleury의 알고리즘?