주어진 수의 노드와 에지로 그래프를 찾는 알고리즘

Question

나는 다수의 노드를 가지고 있고 각 노드는 다수의 에지를 가지고있다. 예 : 노드 A는 3 가장자리를 가지고, B는 2, C는 2, D는 1입니다. 두 노드 사이에 여러 가장자리가없는 가능한 무향 그래프를 찾기 위해 알고리즘을 찾고 있습니다. 이 간단한 예에 대한 해결 방안은 다음과 같습니다의

A 
    /|\ 
/| \ 
B--C D 

그래서이이 3 개 연결을 갖기 때문에, B는 A와 C에 연결되어있는 다른 3 개 노드와 연결되고, D는 A. 접속되어 모든 모서리 모든 노드가 만족되어야합니다. 다른 예 :

A (3), B (3), C (2), D (1) E (1)

용액 :

 A-----D  OR:  A-----E 
    /\     /\ 
/ \     / \ 
    C-----B-----E   C-----B-----D 

따라서, 때로는 거기 여러 솔루션. 그러나 해결책이없는 것보다 가능합니다. A (2), B (2), C (1)

이러한 3 개의 노드와 주어진 수의 가장자리로 그래프를 만드는 방법은 없습니다.

이제이 문제에 대한 가능한 해결책을 찾기위한 알고리즘을 찾고 있습니다. 이미 알려진 문제가 이미 있을까요? 나는 어떤 종류의 도움이나 힌트라도 기쁘게 생각합니다.

Answer 1

이것은 Graph Realization Problem으로 알려져 있습니다.

Erdős–Gallai theorem은 해결할 수있는시기를 결정하기위한 쉽게 코딩 된 기준을 제공하며 Havel–Hakimi algorithm은 그러한 그래프를 구성하는 재귀 적 방법을 제공합니다. Harsfield와 Ringel의 그래프 이론에서 가장 좋아하는 책 중 하나 인 "그래프 이론의 진주"에는 Havel-Hakimi 알고리즘에 대한 좋은 토론이 있습니다.