Pytania otagowane jako graph-theory

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

3
Czy
Oznacz przez minimalny stopień wyjściowy w G , a przez δ - ( G ) minimalny stopień wyjściowy.δ+(G)δ+(G)\delta^+(G)GGGδ−(G)δ−(G)\delta^-(G) W powiązanym pytaniu wspomniałem o rozszerzeniu Ghouili-Houri twierdzenia Diraca o cyklach hamiltonowskich , co sugeruje, że jeśli to G oznacza hamiltonian.δ+(G),δ−(G)≥n2δ+(G),δ−(G)≥n2\delta^+(G),\delta^-(G) \geq \frac{n}{2} W swoim komentarzu Saeed skomentował inne rozszerzenie, które wydaje …
1
Znalezienie podwójnego wykresu
Według książki Topological Graph Theory autorstwa Grossa i Tuckera, biorąc pod uwagę komórkowe osadzenie wykresu na powierzchni (przez „powierzchnię” rozumiem tutaj kulę z pewnymi uchwytami , a poniżej odnosi się do kuli o dokładnie uchwyty), można zdefiniować podwójny multigraf, traktując twarze osadzonego wykresu jako wierzchołki i dodając krawędź między dwoma …
2
„Krewni” problemu najkrótszej ścieżki
Rozważ dołączony niekierowany wykres z nieujemnymi wagami krawędzi i dwoma wyróżnionymi wierzchołkami . Poniżej przedstawiono niektóre problemy ze ścieżką, które mają następującą postać: znajdź ścieżkę , tak aby jakaś funkcja ciężaru krawędzi na ścieżce była minimalna. W tym sensie wszyscy są „krewnymi” problemu najkrótszej ścieżki; w tym ostatnim funkcja jest …
2
Powszechny wgląd w hipotetyczną złożoność problemów graficznych
Natknąłem się na dwa przykłady hipotetycznej twardości niektórych problemów graficznych. Hipotetyczna twardość oznacza, że ​​obalenie niektórych przypuszczeń oznaczałoby zupełność NP odpowiedniego problemu grafowego. Na przykład, hipoteza Barnette'a stwierdza, że ​​każdy 3-połączony sześcienny dwuwymiarowy wykres jest hamiltonianem. Feder i Subi udowodnili, że obalenie przypuszczenia oznaczałoby zupełność NP problemu cyklu hamiltonowskiego na …
1
Klasy wykresów z nadprzyrodzoną szerokością
Istnieje kilka interesujących klas wykresów z ograniczoną szerokością. Na przykład drzewa (treewidth 1), szeregi równoległe wykresy (treewidth 2), zewnętrzne płaszczyzny (treewidth 2), routerplanar wykresy (treewidth O (k)), wykresy szerokości gałęzi (treewidth O (k)), .. .kkkkkk Pytanie: Czy istnieją przykłady interesujących klas wykresów, których szerokość nie jest ograniczona stałą, ale funkcją …
2
Losowy spacer i średni czas trafienia na prostym niekierowanym wykresie
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ ) τGsolGO(τ)O(τ)O(\tau)ττ\tauτ=∑v∈Vπ(v)⋅H(u,v),τ=∑v∈V.π(v)⋅H.(u,v),\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), ππ\pi to rozkład …
2
Czy dziedziczna klasa grafów może zawierać prawie wszystkie, ale nie wszystkie, wykresy n-wierzchołkowe?
Niech będzie dziedziczną klasą grafów. (Dziedziczne = zamknięte w odniesieniu do pobierania indukowane subgraphs). Let oznacza zbiór wykresów -Vertex w . Powiedzmy, że zawiera prawie wszystkie wykresy, jeśli ułamek wszystkich wykresów -vertex przypadających na zbliża się do 1, jako .QQQQnQnQ_nnnnQQQQQQnnnQnQnQ_nn → ∞n→∞n\rightarrow\infty Pytanie: Czy to możliwe, że dziedziczna klasa grafów …
2
Dokładna formuła dla liczby drzew rozpinających prostokąta
Ten blog mówi o generowaniu „krętych małych labiryntów” za pomocą komputera i ich liczeniu. Wyliczenia można dokonać za pomocą algorytmu Wilsona, aby uzyskać UST , ale nie pamiętam wzoru na ich liczbę. http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike Zasadniczo Twierdzenie o Drzewie Matrycowym stwierdza, że ​​liczba drzew spinających na wykresie jest równa wyznacznikowi macierzy Laplaciana …
3
Wykres teoretyczne ograniczenie do dowodów w teorii złożoności dowodu
Złożoność dowodu jest najbardziej podstawowym obszarem teorii złożoności obliczeniowej. Ostatecznym celem tego obszaru jest udowodnienie , co oznacza, że ​​żaden z proverów nie może dać dowodu na niezadowolenie danej formuły wejściowej. N.P.≠ c o NP.N.P.≠dooN.P.NP\neq coNP Wykres jest jednym z formalnych modeli dowodów. Moje pytanie dotyczy dalszego ograniczenia tego modelu. …
2
Kiedy wielomianowy GI oznacza wielomianowy (krawędziowy) GI?
Skrzyżowane z MO . Izomorfizm kolorowego wykresu (krawędzi) to GI, który zachowuje kolory (krawędzi, jeśli jest w kolorze krawędzi). Istnieje kilka obniżek przy użyciu transformacji / gadżetów GI (krawędzi) w kolorze do GI. W przypadku GI w kolorze krawędzi najprostsze jest zastąpienie kolorowej krawędzi gadżetem chroniącym GI kodującym kolor (najłatwiejszym …
1
Ukryta ścieżka w kwadratowych siatkach
Natknąłem się na otwarty problem postawiony przez Davida Eppsteina i jestem zainteresowany jego złożonością. Doszedł do wniosku, że jest kompletny NP. Dane wejściowe: przez macierzy zer i jedynek, sekwencja zer i jedyneknnnnnnn2n2n^2 Pytanie: Czy istnieje ścieżka przez sąsiednie wpisy macierzy, obejmujące każdy wpis macierzy dokładnie raz, a wartości pasują do …
2
Kompletność obejmująca drzewa
Drzewo opinające wykresu nazywane jest drzewem kompletności, jeśli zbiór jego liści indukuje całkowity podrozdział na grafie gospodarza. Biorąc pod uwagę wykres i liczbę całkowitą , jaka jest złożoność decyzji, czy zawiera drzewo kompletności z co najwyżej liści?GsolGkkkGGGkkk Powodem zadawania tego pytania jest to, że odpowiadającym problemem dla drzew niezależności jest …
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.