Problem realizacji digrafu

Problem realizacji digrafu jest problemem decyzyjnym w teorii grafów . Biorąc pod uwagę pary nieujemnych liczb całkowitych $}})}$$\ Displaystyle ((a_ {1}, b_ {1}), \ ldots, (a_ {n}, b_ {$$styl wyświetlania b_{i}}$ , problem polega na pytaniu, czy istnieje oznaczony prosty graf skierowany $,$ taki że każdy $wierzchołek$ ma stopień wejściowy $displaystyle v_ {i}$ stopień wyjściowy .

Rozwiązania

Problem należy do klasy złożoności P. Znane są dwa algorytmy, które to potwierdzają. Pierwsze podejście dają algorytmy Kleitmana-Wanga konstruujące specjalne rozwiązanie z wykorzystaniem algorytmu rekurencyjnego . Drugi to charakterystyka za pomocą twierdzenia Fulkersona – Chena – Anstee , tj. Trzeba zweryfikować $nierówności$ .

Inne oznaczenia

Problem można również przedstawić w kategoriach macierzy zero-jedynkowych . Połączenie można zobaczyć, jeśli zdamy sobie sprawę, że każdy wykres skierowany ma macierz sąsiedztwa , w której sumy kolumn i sumy wierszy odpowiadają ${\ Displaystyle (a_ {1}, \ cdots, a_ {n$ i ${\ Displaystyle (b_ {1}, \ ldots, b_ {n})}$ . Zauważ, że przekątna macierzy zawiera tylko zera. Problem jest wtedy często oznaczany przez macierze 0-1 dla danych sum wierszy i kolumn . W literaturze klasycznej problem ten był niekiedy ujmowany w kontekście tablic kontyngencji przez tablice kontyngencji z zadanymi marginesami .

Powiązane problemy

Podobne problemy opisują ciągi stopni prostych grafów , prostych grafów skierowanych z pętlami i prostych grafów dwudzielnych . Pierwszym problemem jest tak zwany problem realizacji grafu . Drugi i trzeci są równoważne i są znane jako problem realizacji dwudzielnej . Chen (1966) podaje charakterystykę skierowanych multigrafów z ograniczoną liczbą równoległych łuków i pętli do danego ciągu stopni . Dodatkowe ograniczenie cykliczności grafu skierowanego jest znane jako realizacja dag . Nichterlein i Hartung (2012) udowodnili NP-zupełność tego problemu. Berger i Müller-Hannemann (2011) wykazali, że klasa przeciwstawnych sekwencji jest w P . Problem jednolitego próbkowania grafu skierowanego do ustalonej sekwencji stopni polega na skonstruowaniu rozwiązania problemu realizacji digrafu z dodatkowym ograniczeniem, że każde takie rozwiązanie ma takie samo prawdopodobieństwo. Problem ten został pokazany w FPTAS dla regularnych sekwencji przez Catherine Greenhill ( 2011 ). Ogólny problem jest nadal nierozwiązany.

• Chen, Wai-Kai (1966), „O realizacji a ( p , s ) -dwuznaku z określonymi stopniami”, Journal of the Franklin Institute , 103 : 406–422
• Nichterlein, Andrzej; Hartung, Sepp (2012), „NP-Twardość i podatność na zmiany stałych parametrów realizacji sekwencji stopni z ukierunkowanymi wykresami acyklicznymi”, 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 Computational Theory : 264–275
• Greenhill, Catherine (2011), „Wielomian związany z czasem mieszania łańcucha Markowa do próbkowania grafów skierowanych regularnie”, Electronic Journal of Combinatorics , 18