디그람 인식 문제

디그라프 실현 문제는 그래프 이론의 결정 문제다.Given pairs of nonnegative integers ${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$, the problem asks whether there is a labeled simple directed graph such that each vertex ${\displaystyle v_{i}}$ has indegree ${\displaystyle a_{i}}$ and outdegree ${\displaystyle {}_{}}$${\displaystyle b_{}}$ i ${\$

해결 방법

문제는 복잡도 등급 P에 속한다.그것을 증명하는 두 개의 알고리즘이 알려져 있다.첫 번째 접근방식은 Kleitman-Wang 알고리즘이 재귀 알고리즘을 사용하여 특수 솔루션을 구성함으로써 제공된다.두 번째 것은 풀커슨-첸-앤스티 정리에 의한 특성화, 즉 $n{\displaystyle }$ ${\displaystyn n}$ 불평등의$$ 정확성을 검증해야 한다.

기타 표기

그 문제는 또한 제로원 매트릭스로도 명시될 수 있다.The connection can be seen if one realizes that each directed graph has an adjacency matrix where the column sums and row sums correspond to ${\displaystyle (a_{1},\cdots ,a_{n})}$ and ${\displaystyle (b_{1},\ldots ,b_{n})}$. Note that the diagonal of the matrix only contains zeros.그런 다음 주어진 행 및 열 합계에 대해 0-1-매트릭스로 문제를 나타내는 경우가 많다.고전 문헌에서 문제는 때때로 주어진 여백을 가진 분할표에 의해 분할표의 맥락에서 명시되었다.

관련 문제

유사한 문제들은 간단한 그래프, 루프가 있는 간단한 지시 그래프, 그리고 간단한 초당적 그래프의 정도 순서에 대해 설명한다.첫 번째 문제는 이른바 그래프 실현 문제다.두 번째와 세 번째 것은 동등하며 초당적 실현 문제로 알려져 있다.Chen(1966)은 주어진 정도 순서로 평행 호와 루프의 경계 수를 가진 지시된 다중 글자에 대해 특성을 부여한다.지시된 그래프의 평활성의 추가적인 제약조건을 dag 실현이라고 한다.Nichterlein & Hartung(2012)은 이 문제의 NP-완전성을 입증했다.Berger & Müller-Hannemann(2011년)은 반대되는 시퀀스의 클래스가 P에 있음을 보여주었다.지시된 그래프를 고정된 정도 순서에 따라 균일하게 샘플링하는 문제는 그러한 각 솔루션이 동일한 확률로 제공된다는 추가적인 제약조건으로 디그라프 실현 문제에 대한 솔루션을 구축하는 것이다.이 문제는 캐서린 그린힐(2011년)이 정규 시퀀스에 대해 FPTAS에 있는 것으로 나타났다.일반적인 문제는 여전히 해결되지 않고 있다.

참조

• Chen, Wai-Kai (1966), "On the realization of a (p,s)-digraph with prescribed degrees", Journal of the Franklin Institute, 103: 406–422
• Nichterlein, André; Hartung, Sepp (2012), "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs", Journal of the Franklin Institute, 7318: 283–292
• Berger, Annabell; Müller-Hannemann, Matthias (2011), "Dag Realizations of Directed Degree Sequences", Proceedings of the 18th International Conference on Fundamentals of Computation Theory: 264–275
• Greenhill, Catherine (2011), "A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs", Electronic Journal of Combinatorics, 18