แนวคิด
ในส่วนที่เกี่ยวกับกราฟที่ไม่ระบุทิศทางของโหนด b และขอบ ภารกิจคือการกำหนดขอบขั้นต่ำที่จำเป็นในการสร้างวงจรออยเลอร์ในกราฟที่กำหนด
ป้อนข้อมูล
b = 3,
a = 2
Edges[] = {{1, 2}, {2, 3}} ผลผลิต
1
ด้วยการเชื่อมต่อ 1 ถึง 3 เราสามารถสร้างวงจรออยเลอร์ได้
วิธีการ
ในส่วนที่เกี่ยวกับวงจรออยเลอร์ที่มีอยู่ในกราฟ เราต้องการให้ทุกโหนดควรมีระดับที่เท่ากัน เนื่องจากมีขอบที่สามารถนำไปใช้เพื่อออกจากโหนดหลังจากเข้าไปได้
ตอนนี้มีสองกรณี -
การมีอยู่ขององค์ประกอบที่เชื่อมต่อกันในกราฟ
ในกรณีนี้ หากโหนดทั้งหมดในกราฟมีดีกรีคู่ เราก็บอกว่ากราฟมีวงจรออยเลอร์อยู่แล้ว และเราไม่จำเป็นต้องเพิ่มขอบใดๆ เข้าไป แต่ถ้ามีโหนดใดติดตั้งระดับคี่ เราจำเป็นต้องเพิ่มขอบ กราฟยังมีจุดยอดองศาคี่จำนวนคู่ เหตุการณ์นี้สามารถตรวจสอบได้ง่าย ๆ ด้วยข้อเท็จจริงที่ว่าผลรวมขององศาจากโหนดองศาคู่และองศาจากโหนดองศาคี่ควรตรงกับองศารวมที่เสมอแม้ในขณะที่ขอบทุกอันมีส่วนทำให้เกิดผลรวมนี้สอง ด้วยเหตุนี้ หากเราจับคู่โหนดระดับคี่แบบสุ่มในกราฟและเพิ่มขอบระหว่างโหนดเหล่านี้ เราสามารถสร้างโหนดทั้งหมดให้มีดีกรีคู่กันได้ ดังนั้นจึงสร้างวงจรออยเลอร์ได้
การมีอยู่ของส่วนประกอบที่ขาดการเชื่อมต่อในกราฟ
ตอนแรกเราทำเครื่องหมายส่วนประกอบเป็นคี่และคู่ ส่วนประกอบแปลก ๆ คือส่วนประกอบที่มีโหนดระดับคี่ขั้นต่ำหนึ่งโหนด ตอนนี้เรานำองค์ประกอบคู่ทั้งหมดมาและเลือกจุดยอดสุ่มจากทุกองค์ประกอบแล้วจัดเรียงเป็นเส้นตรง ดังนั้น การเพิ่มขอบระหว่างจุดยอดที่อยู่ติดกัน เราจึงเชื่อมต่อองค์ประกอบคู่และสร้างองค์ประกอบคี่ที่เทียบเท่ากันซึ่งมีสองโหนดที่มีดีกรีเป็นคี่
ด้วยเหตุนี้ เพื่อจัดการกับส่วนประกอบที่แปลกประหลาด เช่น ส่วนประกอบที่มีโหนดดีกรีอย่างน้อยหนึ่งโหนด เราสามารถเชื่อมต่อส่วนประกอบแปลก ๆ เหล่านี้ทั้งหมดโดยใช้ขอบที่มีจำนวนเท่ากับจำนวนของส่วนประกอบที่ตัดการเชื่อมต่อ ซึ่งสามารถทำได้โดยการจัดวางส่วนประกอบตามลำดับวงจร และเลือกโหนดระดับคี่สองโหนดจากทุกองค์ประกอบ และใช้สิ่งเหล่านี้เพื่อเชื่อมต่อกับส่วนประกอบที่ด้านใดด้านหนึ่ง ตอนนี้เรามีองค์ประกอบที่เชื่อมต่อเพียงชิ้นเดียวซึ่งเราได้อธิบายไว้
ตัวอย่าง
//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
