Havelアルゴリズムについて度数シーケンスが単純図を構成できるかどうかを判断する思考
問題の説明:
Given a list of n natural numbers d1, d2,...,dn, show how to decide in polynomial time whether there exists an undirected graph G = (V, E) whose node degrees are precisely the numbers d1,d2,···,dn. G should not contain multiple edges between the same pair of nodes, or “loop” edges with both endpoints equal to the same node.
この問題は,度数シーケンスから単純図を構成できるか否かを判断することである.まず、度数の合計が偶数であるかどうかを統計します.これは図の要件です.次にHavelの定理に基づいて,度数シーケンスにn個の数が含まれ,n個のノードに対応し,i番目のノードの度数はdiであると仮定する.次にノードを度数サイズ降順に並べ替え、その後最初のノードを選択し、そのノードの度数がnより大きいと簡単な図を構成できない.そうでなければ、最初のノードの後のd 1ノードを1度ずつ減算し、このプロセスは、そのノードと大きなd 1ノードを接続することと理解することができ、接続中にあるノードの度数が0未満であることが発見された場合、簡単な図を構成することはできない.最初のノードを考慮した後は考慮されず、残りのノードは度降順に並べ替えられ、n=n-1となり、上記の手順を繰り返します.
疑似コードは次のとおりです.
正確性の証明:
アルゴリズムが毎回最大度数の点を選択するのは、後からその点の度数を相殺するのに十分な点があるためであり、まず、このアルゴリズムが除外する場合に単純図を構成できないかどうかを考慮し、その排除条件は度数の総和が偶数でないこと、最大度数がノード数を超えていること、および接続過程で負の度数が現れた点を含み、第1は図を構成できる要件である.2番目の条件は、ノードに必ずリングまたは平行エッジが存在することを示し、3番目の条件は孤立ノードが接続されていることを示し、これは許されないため、図には必ずリングまたは平行エッジが現れている.したがって,このアルゴリズムが除外する場合は,単純図を構成できない場合である.
では,このアルゴリズムが正常に決定したシーケンスが単純図を構成できない場合があるのだろうか.これは明らかに不可能である.任意の単純な図が各ノードに接続されているのは、度数がそれより小さくないノードの単純な図に変換できるからである.例えば、まずランダムに1つのノードを見つけ、他のd 1ノードを接続し、その後、そのノードを考慮せず、残りのノードの中で度数が最大のノードを探し、2番目に大きい度数、すなわちd 2ノードに接続する.すべての度数が割り当てられるまで、このように類推します.
以上のように,このアルゴリズムは正しい.複雑度分析:
1つの遍歴に1つのソートがネストされているので,アルゴリズムの時間的複雑さはO(n 2 logn)である.
Given a list of n natural numbers d1, d2,...,dn, show how to decide in polynomial time whether there exists an undirected graph G = (V, E) whose node degrees are precisely the numbers d1,d2,···,dn. G should not contain multiple edges between the same pair of nodes, or “loop” edges with both endpoints equal to the same node.
この問題は,度数シーケンスから単純図を構成できるか否かを判断することである.まず、度数の合計が偶数であるかどうかを統計します.これは図の要件です.次にHavelの定理に基づいて,度数シーケンスにn個の数が含まれ,n個のノードに対応し,i番目のノードの度数はdiであると仮定する.次にノードを度数サイズ降順に並べ替え、その後最初のノードを選択し、そのノードの度数がnより大きいと簡単な図を構成できない.そうでなければ、最初のノードの後のd 1ノードを1度ずつ減算し、このプロセスは、そのノードと大きなd 1ノードを接続することと理解することができ、接続中にあるノードの度数が0未満であることが発見された場合、簡単な図を構成することはできない.最初のノードを考慮した後は考慮されず、残りのノードは度降順に並べ替えられ、n=n-1となり、上記の手順を繰り返します.
疑似コードは次のとおりです.
total_degree = sum(d)
if !total_degree % 2:
print 'no graph'
return -1
n = length(d)
while(n):
sort(d)
d1 = d[0]
if d1 > n:
print 'no simple graph'
return -1
for i = 1 to d1:
d[i] -= 1
if d[i] < 0:
print 'no simple graph'
return -1
d[0] = 0
n -= 1
print 'the sequence can construct a simple graph’正確性の証明:
アルゴリズムが毎回最大度数の点を選択するのは、後からその点の度数を相殺するのに十分な点があるためであり、まず、このアルゴリズムが除外する場合に単純図を構成できないかどうかを考慮し、その排除条件は度数の総和が偶数でないこと、最大度数がノード数を超えていること、および接続過程で負の度数が現れた点を含み、第1は図を構成できる要件である.2番目の条件は、ノードに必ずリングまたは平行エッジが存在することを示し、3番目の条件は孤立ノードが接続されていることを示し、これは許されないため、図には必ずリングまたは平行エッジが現れている.したがって,このアルゴリズムが除外する場合は,単純図を構成できない場合である.
では,このアルゴリズムが正常に決定したシーケンスが単純図を構成できない場合があるのだろうか.これは明らかに不可能である.任意の単純な図が各ノードに接続されているのは、度数がそれより小さくないノードの単純な図に変換できるからである.例えば、まずランダムに1つのノードを見つけ、他のd 1ノードを接続し、その後、そのノードを考慮せず、残りのノードの中で度数が最大のノードを探し、2番目に大きい度数、すなわちd 2ノードに接続する.すべての度数が割り当てられるまで、このように類推します.
以上のように,このアルゴリズムは正しい.複雑度分析:
1つの遍歴に1つのソートがネストされているので,アルゴリズムの時間的複雑さはO(n 2 logn)である.