C++でオイラー回路を作成するために追加する必要のある最小エッジ
bノードとエッジの特定の無向グラフに関して、仕事は、特定のグラフでオイラー回路を構築するために必要な最小エッジを決定することです。
入力
b = 3,
a = 2
Edges[] = {{1, 2}, {2, 3}} 出力
1
1対3を接続することで、オイラー回路を構築できます。
メソッド
グラフに存在するオイラー回路に関しては、ノードに入った後にノードを出るために適用できるエッジが存在するため、すべてのノードが偶数次である必要があります。
現在、2つのケースが考えられます-
グラフ内の1つの連結成分の存在
この場合、グラフ内のすべてのノードに等次数が装備されている場合、グラフにはすでにオイラー回路があり、エッジを追加する必要はありません。ただし、奇数次数を備えたノードがある場合は、エッジを追加する必要があります。グラフには、奇数次数の頂点がいくつでも存在する可能性があります。このインシデントは、偶数度ノードからの度の合計と奇数度ノードからの度の合計が、すべてのエッジがこの合計に2を与えるため、常に偶数である合計度と一致する必要があるという事実によって簡単に確認できます。この結果、グラフ内のランダムな奇数次数ノードをペアにしてそれらの間にエッジを追加すると、すべてのノードが偶数次数になるように構築できるため、オイラー回路が存在します。
グラフ内の切断されたコンポーネントの存在
最初に、コンポーネントを奇数と偶数としてマークします。奇数コンポーネントは、最小1つの奇数次ノードを持つコンポーネントです。ここで、すべての偶数コンポーネントを取得し、すべてのコンポーネントからランダムな頂点を選択して、それらを線形に配置します。したがって、隣接する頂点の間にエッジを追加して、偶数のコンポーネントを接続し、奇数の次数を持つ2つのノードを持つ同等の奇数のコンポーネントを作成しました。
この結果、奇数のコンポーネント、つまり最小1つの奇数次ノードを持つコンポーネントを処理するために、切断されたコンポーネントの数に等しい数のエッジを適用して、これらすべての奇数のコンポーネントを接続できます。これは、コンポーネントを循環順序で配置し、すべてのコンポーネントから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
-
グラフを切断するためにカットするエッジの最小数を見つけるC++プログラム
このプログラムでは、グラフのエッジ接続を見つける必要があります。グラフのグラフのエッジ接続は、それがブリッジであることを意味し、グラフを削除すると切断されます。接続されたコンポーネントの数は、切断された無向グラフのブリッジを削除すると増加します。 関数と擬似コード Begin Function connections() is a recursive function to find out the connections: A) Mark the current node un visited. B) Initia
-
Pythonでオイラー回路を作成するために追加する必要のある最小エッジ
b個のノードと数個のエッジの無向グラフがあるとします。このグラフでオイラー回路を構築するために必要な最小エッジを見つける必要があります。 したがって、入力が次のような場合 その場合、出力は1になります。 これを解決するには、次の手順に従います- 関数dfs（）を定義します。これには、g、visit、odd_vert、degree、comp、vが必要です visit [v]：=1 次数[v]mod2が1と同じ場合、 odd_vert [comp]：=odd_vert [comp] + 1 範囲0からg[v]のサイズのuの場合、実行 visit [u]が0と同じ場合、