3

次の値のうち、6つの頂点を持つ無向グラフの次数になり得るものを見つける必要があります。

a）3 2 2 2 3 3
b）4 2 2 2 3 2
c）5 2 2 2 0 3
d）5 2 2 2 1 2

私が見つけた唯一の方法は、1枚の紙にグラフを描いて、それが可能かどうかを確認することです。可能であれば、各グラフを描画する以外の方法で、この問題を開始するためのヒントが必要です。

4

2 に答える 2

12

次のアルゴリズムは、指定されたノード度で単純なグラフを作成できるかどうかを決定します。

  1. 度を降順で並べ替えます

  2. 最初の次数が0（つまりすべての次数が0）の場合、明らかにそのようなグラフを作成でき（エッジなし）、完了です。

  3. 最初の度の値がd（> 0）の場合、次のd度は0より大きい必要があります。そうでない場合は、そのようなグラフを作成できません。

  4. 最初の次数（値）を取り除き、次の次数を1つd減らしますd（つまり、要求された数のエッジを、最も高い次数のノードから残りのノードの中で最も高い次数のノードに描画します。この仮定の正確さについては、以下の証明を参照してください）。次に、ステップ1に進みます（ノードが1つ少なくなります）。

例a）（重みの合計が奇数であるため拒否される可能性がありますが、上記のアルゴリズムも機能します）

3 2 2 2 3 3
3 3 3 2 2 2
  2 2 1 2 2
  2 2 2 2 1
    1 1 2 1
    2 1 1 1
      0 0 1
      1 0 0
        -1   not possible

例c）

5 2 2 2 0 3
5 3 2 2 2 0
  2 1 1 1 -1   not possible

例d）

5 2 2 2 1 2 
5 2 2 2 2 1
  1 1 1 1 0
    0 1 1 0
    1 1 0 0
      0 0 0  ok

欠落しているのは、与えられたノード度でグラフを描画できる場合、一致するグラフの1つがステップ4のこのプロパティを持っていること、つまり、最も高い次数のノードが次に高い次数のノードに接続されていることの証明です。

したがって、それAが最高次数のノードであり、次数がAに接続されていないノードBの次数よりも小さいノードに接続されていると仮定します。したがって、に接続されている別のノードがあります。したがって、エッジがあり、ノードの角度を変更せずに、egesで置き換えることができます。Cdegree(B) > 0degree(C) > 1DCABCDACBD

この手順を十分な回数繰り返すことにより、次に高い次数を持つすべてのノードを最も高い次数を持つノードに接続することができます。

于 2013-02-06T19:41:37.597 に答える
2

この場合、握手補題または次数和の式が必要十分条件です。これは、無向グラフを形成することだけを考慮しているためです（エッジの方向は重要ではありませんが、ループまたは平行エッジについては何も言われていません）。したがって、オプションcとオプションdは有効な6頂点無向グラフです。

質問が単純な無向グラフ（ループと平行辺は許可されていない）を求めている場合は、@coprocで説明されているHavel/ Hakimiによるアルゴリズムを導入する必要があります。

于 2013-02-07T04:28:16.447 に答える