Pytania otagowane jako graph-theory

Teoria grafów to nauka o grafach, strukturach matematycznych wykorzystywanych do modelowania parowania relacji między obiektami.

4
Zliczanie liczby osłon wierzchołków: kiedy jest to trudne?
Rozważmy problem # P-zupełny liczenia liczby osłon wierzchołków danego wykresu G=(V,E)G=(V,E)G = (V, E) . Chciałbym wiedzieć, czy jest jakikolwiek wynik pokazujący, jak twardość takiego problemu zmienia się w zależności od parametru (na przykład ).GGGd=|E||V|d=|E||V|d = \frac{|E|}{|V|} Mam wrażenie, że problem powinien być łatwiejszy zarówno wtedy, gdy jest rzadki, jak …
2
Uogólnienie węgierskiego algorytmu na ogólne niekierowane wykresy?
Algorytm węgierski jest kombinatorycznym algorytmem optymalizacyjnym, który rozwiązuje problem dwustronnego dopasowania maksymalnej masy w czasie wielomianowym i przewidywał późniejszy rozwój ważnej metody pierwotnej podwójnej . Algorytm został opracowany i opublikowany przez Harolda Kuhna w 1955 r., Który nadał mu nazwę „algorytm węgierski”, ponieważ algorytm był oparty na wcześniejszych pracach dwóch …
2
Uzasadnienie metody węgierskiej (Kuhn-Munkres)
Napisałem implementację algorytmu Kuhna-Munkresa dla problemu dwustronnego idealnego dopasowania minimalnej wagi w oparciu o notatki z wykładu, które znalazłem tu i tam w Internecie. Działa naprawdę dobrze, nawet na tysiącach wierzchołków. I zgadzam się, że teoria jest naprawdę piękna. A jednak wciąż zastanawiam się, dlaczego musiałem tak bardzo się starać. …
1
Generowanie wykresów za pomocą trywialnych automorfizmów
Sprawdzam jakiś model kryptograficzny. Aby pokazać jego nieadekwatność, opracowałem wymyślony protokół oparty na izomorfizmie grafowym. Zakładanie istnienia algorytmów BPP zdolnych do generowania „trudnych wystąpień problemu z izomorfizmem grafów” jest „powszechne” (a jednak kontrowersyjne!). (Wraz ze świadkiem izomorfizmu). W moim skonstruowanym protokole założę istnienie takich algorytmów BPP, które spełniają jeden dodatkowy …
2
Optymalny algorytm znajdowania obwodu rzadkiego wykresu?
Zastanawiam się, jak znaleźć obwód rzadkiego niekierowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy w , to znajdę obwód …
2
Liczba minut wykresu bez użycia algorytmu Kargera
Wiemy, że algorytm wycinania Kargera można wykorzystać do udowodnienia (w niekonstruktywny sposób), że maksymalna liczba możliwych skrótów może mieć wykres ( n2))(n2))n \choose 2 . Zastanawiałem się, czy moglibyśmy w jakiś sposób udowodnić tę tożsamość, podając bijectywny (raczej iniekcyjny) dowód z zestawu skrótów do innego zestawu liczności ( n2))(n2))n \choose …
1
Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest trudne (łatwe)?
Treewith jest ważnym parametrem grafu, który wskazuje, jak blisko wykres jest od drzewa (choć nie w ścisłym sensie topologicznym). Powszechnie wiadomo, że obliczenie szerokości jest trudne dla NP. Czy są jakieś naturalne klasy wykresów, w których trudno jest obliczyć szerokość ? Podobnie: Czy istnieją ciekawe klasy grafów, w których obliczanie …
1
Dla których wykresów drzewo DFS jest zawsze ścieżką?
Dla których niekierowanych wykresów są wszystkie drzewa pierwszego wyszukiwania głębokości (dla wszystkich możliwych wierzchołków początkowych i dla wszystkich wyborów, których sąsiadów najpierw szukać) ścieżki skierowane? Oznacza to, że każde drzewo DFS powinno mieć tylko jeden liść, a każdy inny wierzchołek powinien mieć dokładnie jedno dziecko. Dotyczy to na przykład cykli, …
1
Trudne problemy z rozszerzalnością
W przypadku problemu z rozszerzeniem otrzymujemy część rozwiązania i chcemy zdecydować, czy możemy go rozszerzyć do kompletnego rozwiązania. Niektóre problemy związane z rozszerzalnością można skutecznie rozwiązać, podczas gdy inne problemy z możliwością rozbudowy przekształcają problem łatwy w trudny. Na przykład twierdzenie Koniga-Halla stwierdza, że ​​wszystkie sześcienne dwustronne wykresy można pokolorować …
1
Podział na wykresy interwałowe
Załóżmy, że istnieje wykres . Chcę sprawdzić, czy można podzielić na dwa rozłączne zestawy i tak, że podgrupy indukowane przez i są wykresami interwałów jednostkowych.G=(V,E)G=(V,E)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Wiem o kompletności NP określania liczb przedziałów, ale powyższy problem jest inny. Teraz w literaturze znalazłem tę pracę A. Gyárfás i D. Westa na wykresach …
2
Minimalna ilość kolorów zapobiegająca równobocznemu jednokolorowemu podtrószkowi
W Bundeswettberweb Infomatik 2010/2011 pojawił się interesujący problem: Dla stałej znajdź minimalne i mapę , tak że nie ma potrójnego z .nnnkkkφ:{(i,j)|i≤j≤n}→{1,…,k}φ:{(i,j)|i≤j≤n}→{1,…,k}\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}(i,j),(i+l,j),(i+l,j+l)(i,j),(i+l,j),(i+l,j+l)(i,j),(i+l,j),(i+l,j+l)φ(i,j)=φ(i+l,j)=φ(i+l,j+l)φ(i,j)=φ(i+l,j)=φ(i+l,j+l)\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l) Mianowicie szukamy minimalnej ilości kolorów dla trójkąta, tak aby nie było równomiernego podtekstu równobocznego (poniższy rysunek pokazuje nieprawidłowe zabarwienie, ponieważ podświetlone wierzchołki tworzą …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.