ハンドシェイク理論は次数和定理またはハンドシェイク補題とも呼ばれます。ハンドシェイク理論では、グラフのすべての頂点の次数の合計は、そのグラフに含まれるエッジの数の 2 倍になると述べられています。ハンドシェイク理論の記号表現は次のように説明されます。
ここ、
「d」は頂点の次数を示すために使用されます。
「v」は頂点を示すために使用されます。
「e」はエッジを示すために使用されます。
ハンドシェイク定理:
ハンドシェイク定理には、次のように説明される結論がいくつかあります。
どのグラフでも次のようになります。
- すべての頂点の次数の合計は偶数でなければなりません。
- すべての頂点の次数が奇数である場合、これらの頂点の次数の合計は常に偶数のままでなければなりません。
- 奇数次数の頂点がいくつかある場合、これらの頂点の数は偶数になります。
ハンドシェイク理論の例
ハンドシェイク理論にはさまざまな例があり、その例のいくつかを次のように説明します。
例 1: ここでは、各頂点の次数が 4 エッジと 24 エッジであるグラフがあります。次に、このグラフの頂点の数を調べます。
解決： 上のグラフを利用すると、次の詳細が得られます。
各頂点の次数 = 24
ハローワールドジャワ
エッジの数 = 24
ここで、頂点の数 = n と仮定します。
ハンドシェイク定理の助けを借りて、次のことがわかります。
すべての頂点の次数の合計 = 2 * エッジの数
ここで、指定された値を上記のハンドシェイク式に代入します。
n*4 = 2*24
n = 2*6
n = 12
したがって、グラフ G では、頂点の数 = 12 になります。
例 2: ここには、21 個のエッジ、次数 4 の頂点 3 つ、および次数 2 の他のすべての頂点を持つグラフがあります。次に、このグラフ内の頂点の合計数を調べます。
キツネ対オオカミ
解決： 上のグラフを利用すると、次の詳細が得られます。
次数 4 の頂点の数 = 3
エッジの数 = 21
他のすべての頂点は次数 2 です
ここで、頂点の数 = n と仮定します。
ハンドシェイク定理の助けを借りて、次のことがわかります。
すべての頂点の次数の合計 = 2 * エッジの数
ここで、指定された値を上記のハンドシェイク式に代入します。
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
したがって、グラフ G では、頂点の総数 = 18 になります。
例 3: ここには、35 個のエッジ、次数 5 の頂点が 4 つ、次数 4 の頂点が 5 つ、次数 3 の頂点が 4 つあるグラフがあります。次に、このグラフ内の次数 2 の頂点の数を調べます。
解決： 上のグラフを利用すると、次の詳細が得られます。
エッジの数 = 35
Cプログラミングのサンプルプログラム
次数 5 の頂点の数 = 4
次数 4 の頂点の数 = 5
次数 3 の頂点の数 = 4
ここで、次数 2 の頂点の数 = n と仮定します。
ハンドシェイク定理の助けを借りて、次のことがわかります。
すべての頂点の次数の合計 = 2 * エッジの数
ここで、指定された値を上記のハンドシェイク式に代入します。
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
FCF
したがって、グラフ G では、次数 2 の頂点の数 = 9 になります。
例 4: ここでは、24 個のエッジを持つグラフがあり、各頂点の次数は k です。次に、指定されたオプションから可能な頂点の数を調べます。
- 15
- 二十
- 8
- 10
解決： 上のグラフを利用すると、次の詳細が得られます。
エッジの数 = 24
各頂点の次数 = k
ここで、頂点の数 = n と仮定します。
ハンドシェイク定理の助けを借りて、次のことがわかります。
すべての頂点の次数の合計 = 2 * エッジの数
ここで、指定された値を上記のハンドシェイク式に代入します。
N*k = 2*24
K = 48/約
頂点の次数には整数が含まれることが必須です。
したがって、上記の方程式では、k の全体の値を提供するタイプの n の値のみを使用できます。
Javaの部分文字列メソッド
ここで、次のように n の位置に 1 つずつ入れて、上記のオプションを確認します。
- n = 15 の場合、k = 3.2 が得られますが、これは整数ではありません。
- n = 20 の場合、k = 2.4 が得られますが、これは整数ではありません。
- n = 8 の場合、k = 6 が得られますが、これは整数であり、許可されます。
- n = 10 の場合、k = 4.8 が得られますが、これは整数ではありません。
したがって、正しい選択肢は選択肢 C です。