Khái niệm
Đối với một đồ thị vô hướng nhất định của b nút và một cạnh, công việc là xác định các cạnh tối thiểu cần thiết để xây dựng Mạch Euler trong đồ thị đã cho.
Đầu vào
b = 3,
a = 2
Edges[] = {{1, 2}, {2, 3}} Đầu ra
1
Bằng cách kết nối 1 đến 3, chúng ta có thể xây dựng một mạch Euler.
Phương pháp
Đối với một Mạch Euler tồn tại trong biểu đồ, chúng ta cần rằng mọi nút phải có độ đều bởi vì khi đó tồn tại một cạnh có thể được áp dụng để thoát ra khỏi nút sau khi nhập nó.
Bây giờ, có thể có hai trường hợp -
Sự tồn tại của một thành phần được kết nối trong biểu đồ
Đối với trường hợp này, nếu tất cả các nút trong biểu đồ được trang bị bằng độ chẵn thì chúng tôi nói rằng biểu đồ đã có Mạch Euler và chúng tôi không yêu cầu thêm bất kỳ cạnh nào trong đó. Nhưng nếu có bất kỳ nút nào được trang bị bậc lẻ, chúng ta yêu cầu thêm các cạnh. Sự cố này có thể dễ dàng được xác minh bằng thực tế rằng tổng độ từ nút độ chẵn và độ từ nút độ từ phải khớp với tổng độ luôn luôn chẵn vì mọi cạnh đóng góp hai vào tổng này. Do đó, nếu chúng ta ghép nối các nút có mức độ lẻ ngẫu nhiên trong biểu đồ và thêm một cạnh giữa chúng, chúng ta có thể xây dựng tất cả các nút để có mức độ chẵn và do đó xây dựng một mạch Euler tồn tại.
Sự tồn tại của các thành phần bị ngắt kết nối trong biểu đồ
Lúc đầu, chúng tôi đánh dấu thành phần là lẻ và chẵn. Các thành phần kỳ lạ là những thành phần có nút mức độ lẻ nhỏ nhất trong chúng. Bây giờ chúng ta lấy tất cả các thành phần chẵn và chọn một đỉnh ngẫu nhiên từ mọi thành phần và sắp xếp chúng theo tuyến tính. Vì vậy, thêm một cạnh giữa các đỉnh liền kề, chúng tôi đã kết nối các thành phần chẵn và xây dựng một thành phần lẻ tương đương có hai nút có mức độ lẻ.
Kết quả là, để đối phó với các thành phần lẻ, tức là các thành phần có tối thiểu một nút bậc lẻ, chúng ta có thể kết nối tất cả các thành phần lẻ này áp dụng các cạnh có số lượng bằng số thành phần bị ngắt kết nối. Điều này có thể được thực hiện bằng cách đặt các thành phần theo thứ tự tuần hoàn và chọn hai nút bậc lẻ từ mọi thành phần và áp dụng chúng để kết nối với các thành phần ở hai bên. Bây giờ chúng tôi có một thành phần được kết nối duy nhất mà chúng tôi đã giải thích.
Ví dụ
//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;
} Đầu ra
1