Rekonstrukcja wykresów z rozkładu stopni

Biorąc pod uwagę rozkład stopni, jak szybko możemy zbudować wykres zgodny z danym rozkładem stopni? Szkic łącza lub algorytmu byłby dobry. Algorytm powinien zgłaszać „brak”, ponieważ nie można zbudować żadnego wykresu i dowolnego przykładu, jeśli można zbudować wiele wykresów.

algorithms graphs graph-theory singhsumit
źródło

Witamy! Jak podaje się „rozkład stopni”? Jako rozkład stochastyczny, jako lista stopni ...?

Raphael

Zobacz ćwiczenie 2.6 tutaj . Podano algorytm tworzenia wykresu z podanej sekwencji stopni.

utdiscant

Aby wyjaśnić komentarz Rafaela, kiedy czytam rozkład stopni , myślę o rozkładzie probabilistycznym stopni. Jak wspominał, kolejność stopni jest prawdopodobnie tym, czego chcesz. Jeśli masz na myśli sens probabilistyczny, prawdopodobnie szukasz jakiegoś losowego algorytmu konstrukcyjnego, który próbuje „przybliżyć” rozkład. Jednak nie ma dla mnie sensu „zgłaszać nie” w tym ustawieniu, ponieważ myślę, że większość wykresów będzie czymś odstającym?

Lucas Cook

A jeśli naprawdę chcesz wygenerować wykres z danym rozkładem stopni, to ten papier wydaje się być dobrym rozwiązaniem. Wygląda na to, że algorytm opisany w poprzednim komentarzu jest w rzeczywistości algorytmem Havla-Hakimi w odpowiedzi Wu Yin.

utdiscant

Odpowiedzi:

Jeśli masz na myśli, jak skonstruować taki prosty wykres (bez pętli własnych i bez równoległych krawędzi), być może twierdzenie Havla-Hakimi jest tym, czego szukasz. Możesz go wyszukać sam, a strona Wikipedii Stopień (teoria grafów) jest również pomocna.

Wu Yin
źródło

dzięki. tak, strona wiki jest w tym przypadku pomocna.

singhsumit

Jeśli rozkład stopni podano jako listę stopni, możesz wykonać następujące czynności, podając węzłów o stopniach : $n$ $d_1, ... ,d_n$

Utwórz pełny wykres na usługach. Dla każdego wierzchołka w podziel go na kopie . Podział tutaj oznacza, utwórz liczbę kopii z krawędziami do każdego wierzchołka ma krawędź do, ale bez krawędzi do innych kopii . Jeśli po prostu usuń wierzchołek. Na nowym wykresie wywołaj te wierzchołki dla . $K_n$ $n$ $v_i$ $K_n$ $d_i$ $v_i$ $v_i$ $d_i = 0$ $v_{ij}$ $1 \leq j \leq d_i$

Po zakończeniu masz bardzo gęsty wykres na wierzchołkach ; nazwać wykres . Wybierz swój ulubiony algorytm dopasowywania maksymalnej (od wykres jest tak gęsta, powinieneś wykorzystać jeden z algorytmów szybkiego mnożenia macierzy opartych) i uruchomić go na . Będzie to powrót pasujący . Jeśli dopasowanie nie jest idealne (tzn. Jeśli nie obejmuje wszystkich wierzchołków), wówczas twój rozkład stopnia był niemożliwy; więc powrót nie . $N = d_1 + ... + d_n$ $H$ $H$ $M$

Jeśli masz idealne dopasowanie , a następnie usunąć wszystkie krawędzie nie w z , a następnie za każdy scalić dużo wierzchołków w jednym wierzchołkiem . Scalenie dwóch wierzchołków oznacza połączenie ich w jeden, tak że wynikowy wierzchołek ma krawędzie do każdego wierzchołka, do którego przynajmniej jeden oryginał miał krawędź. Wywołaj wynikowy wykres ; ma pożądany rozkład stopni. $M$ $M$ $H$ $1 \leq i \leq n$ $d_i$ $v_{i1}, ... , v_{id_i}$ $u_i$ $G$

Wynikowym środowiskiem uruchomieniowym jest gdzie jest stałą dla najszybszego algorytmu mnożenia macierzy (która w momencie pisania wynosi około ). Pod względem liczby wierzchołków na wynikowym wykresie, w najgorszym przypadku gęstego rozkładu stopni mamy . $O(N^\omega)$ $\omega$ $2.373$ $O(n^{2\omega})$

Artem Kaznatcheev
źródło

Z twojego (dość jasnego) wyjaśnienia wcale nie jest jasne, dlaczego mnożenie macierzy wchodzi w równanie.

Raphael

Mnożenie macierzy @Raphael jest jednym ze sposobów rozwiązania maksymalnego dopasowania i jest preferowaną metodą dla gęstych wykresów, ponieważ najlepsza wersja algorytmu dopasowania Edmondsa działa w co dałoby dla tego problemu, ponieważ jest dość gęsty. Więc jeśli masz dostęp do dobrego szybkiego mnożenia macierzy (lub pracując z językiem zorientowanym na matrycę, takim jak Matlab), użyłbym podejścia Muchy i Sankowskiego do dopasowywania.

O (\sqrt{| V |} | E |)

$O(\sqrt{|V|}|E|)$

O (N^{2.5})

$O(N^{2.5})$

H

$H$

Artem Kaznatcheev