개념
b 노드와 a 간선의 주어진 무방향 그래프와 관련하여 주어진 그래프에서 오일러 회로를 구축하는 데 필요한 최소 간선을 결정하는 작업입니다.
입력
b = 3,
a = 2
Edges[] = {{1, 2}, {2, 3}} 출력
1
1~3을 연결하면 오일러 회로를 만들 수 있습니다.
방법
그래프에 오일러 회로가 존재하기 위해서는 모든 노드가 짝수 차수를 가져야 합니다. 그 이유는 노드에 들어간 후 노드를 빠져나가기 위해 적용될 수 있는 간선이 있기 때문입니다.
이제 두 가지 경우가 있을 수 있습니다. -
그래프에서 하나의 연결된 구성 요소의 존재
이 경우와 관련하여 그래프의 모든 노드에 짝수 차수가 장착되어 있으면 그래프에 이미 오일러 회로가 있으며 가장자리를 추가할 필요가 없다고 합니다. 그러나 홀수 차수가 장착된 노드가 있으면 가장자리를 추가해야 합니다. 그래프에 홀수 차수 정점이 존재할 수 있습니다. 이 사건은 짝수 도 노드와 홀수 도 노드의 도 합계가 모든 모서리가 이 합계에 2를 기여하므로 항상 짝수인 총 도와 일치해야 한다는 사실로 쉽게 확인할 수 있습니다. 결과적으로 그래프에서 임의의 홀수 차수 노드를 쌍으로 연결하고 그 사이에 간선을 추가하면 모든 노드가 짝수차를 갖도록 구축할 수 있으므로 오일러 회로가 존재하게 됩니다.
그래프에서 연결이 끊긴 구성 요소의 존재
처음에는 구성 요소를 홀수 및 짝수로 표시합니다. 홀수 구성 요소는 최소 하나의 홀수 차수 노드가 있는 구성 요소입니다. 이제 모든 짝수 구성 요소를 선택하고 모든 구성 요소에서 임의의 정점을 선택하고 선형으로 정렬합니다. 따라서 인접한 정점 사이에 가장자리를 추가하여 짝수 구성 요소를 연결하고 홀수 차수를 가진 두 개의 노드가 있는 동등한 홀수 구성 요소를 만들었습니다.
결과적으로 홀수 구성 요소, 즉 최소 하나의 홀수 차수 노드가 있는 구성 요소를 처리하기 위해 연결이 끊긴 구성 요소의 수와 동일한 수의 가장자리를 적용하여 이러한 모든 홀수 구성 요소를 연결할 수 있습니다. 이것은 구성 요소를 순환 순서로 배치하고 모든 구성 요소에서 두 개의 홀수 차수 노드를 선택하고 이를 적용하여 양쪽의 구성 요소에 연결하여 수행할 수 있습니다. 이제 우리는 우리가 설명한 단일 연결된 구성 요소를 갖게 되었습니다.
예시
//This C++ program finds minimum edge required
// to make Euler Circuit
#include <bits/stdc++.h>
using namespace std;
// This Depth-First Search finds a connected
// component
void dfs1(vector<int> g1[], int vis1[], int odd1[],
int deg1[], int comp, int v){
vis1[v] = 1;
if (deg1[v]%2 == 1)
odd1[comp]++;
for (int u : g1[v])
if (vis1[u] == 0)
dfs1(g1, vis1, odd1, deg1, comp, u);
}
// We return minimum edge required to build Euler
// Circuit
int minEdge1(int n, int m, int s1[], int d1[]){
// g1 : to store adjacency list
// representation of graph.
// e1 : to store list of even degree vertices
// o1 : to store list of odd degree vertices
vector<int> g1[n+1], e1, o1;
int deg1[n+1]; // Degrees of vertices used
int vis1[n+1]; // To store visited in DFS
int odd1[n+1]; // Number of odd nodes in components
memset(deg1, 0, sizeof(deg1));
memset(vis1, 0, sizeof(vis1));
memset(odd1, 0, sizeof(odd1));
for (int i = 0; i < m; i++){
g1[s1[i]].push_back(d1[i]);
g1[d1[i]].push_back(s1[i]);
deg1[s1[i]]++;
deg1[d1[i]]++;
}
// This 'ans' is result and 'comp' is component id
int ans = 0, comp = 0;
for (int i = 1; i <= n; i++){
if (vis1[i]==0){
comp++;
dfs1(g1, vis1, odd1, deg1, comp, i);
// We check that if connected component
// is odd.
if (odd1[comp] == 0)
e1.push_back(comp);
// We check that if connected component
// is even.
else
o1.push_back(comp);
}
}
// It has been seen that if whole graph is a single connected
// component with even degree.
if (o1.size() == 0 && e1.size() == 1)
return 0;
// It has been seen that if all connected component is even
if (o1.size() == 0)
return e1.size();
//It has been seen that if graph have atleast one even connected
// component
if (e1.size() != 0)
ans += e1.size();
// For all the odd connected component.
for (int i : o1)
ans += odd1[i]/2;
return ans;
}
// Driven Program
int main(){
int b = 3, a = 2;
int source1[] = { 1, 2 };
int destination1[] = { 2, 3 };
cout << minEdge1(b, a, source1, destination1) << endl;
return 0;
} 출력
1