Pytania otagowane jako graph-theory

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

1
Czy istnieje algorytm, który wyszukuje zakazanych nieletnich?
Twierdzenie Robertsona-Seymour'a głosi, że każda niewielka, zamknięta rodzinasolG\mathcal G wykresów można scharakteryzować przez skończoną liczbę zakazanych nieletnich. Czy istnieje algorytm wejściowy solG\mathcal G wypuszcza zakazanych nieletnich, czy jest to nierozstrzygalne? Oczywiście odpowiedź może zależeć od tego, w jaki sposób solG\mathcal Gjest opisany na wejściu. Na przykład jeślisolG\mathcal G jest podany …
1
Co wiadomo na temat twardości wskaźnika chromatycznego dla ograniczonych klas grafów?
Jest ładny papier z 1991 roku, który zawiera trzy diagramy dotyczące różnych rodzin klas grafów, pokazujące, co wiadomo na temat twardości wyznaczania dla nich indeksu chromatycznego. Czy są odtąd jakieś wiadomości na ten temat? Najbardziej interesuje mnie to, co wiadomo na temat wykresów z ograniczoną liczbą chromatyczną. Moja ciekawość została …
1
Złożoność homomorfizmu digrafa w cyklu zorientowanym
Biorąc pod uwagę stałą skierowane wykres (digrafu) The -COLORING problem decyzyjny pyta czy digrafu wejście ma homomorfizm do . (Homomorfizmem od do jest odwzorowaniem od do , która chroni łuki, to znaczy, gdy jest łukiem , a jest łukiem )DDDDDDGGGDDDGGGDDDfffV(G)V(G)V(G)V(D)V(D)V(D)uvuvuvGGGf(u)f(v)f(u)f(v)f(u)f(v)DDD Klasa problemów COLORING jest silnie związana z hipotezą dychotomii dla …
1
Reżyserowane multigrafie jako minimalne automaty
Biorąc pod uwagę zwykły język L.LL na alfabecie ZAAA, jego minimalny deterministyczny automat może być postrzegany jako ukierunkowana połączona multigraf ze stałym stopniem | A ||A||A|i zaznaczony stan początkowy (poprzez zapomnienie etykiet przejść, stanów końcowych). Zachowujemy stan początkowy, ponieważ każdy wierzchołek musi być z niego dostępny. Czy odwrotność jest prawdziwa? …
2
Liczba automorfizmów wykresu dla izomorfizmu grafowego
Niech i będą dwoma połączonymi wykresami regularnymi o rozmiarze . Niech być zbiorem permutacji tak, że . Jeśli następnie jest zestaw automorfizmy o .GGGHHHrrrnnnAAAPPPPGP−1=HPGP−1=HPGP^{-1}=HG=HG=HG=HAAAGGG Jaka jest najbardziej znana górna granica rozmiaru ? Czy są jakieś wyniki dla poszczególnych klas grafów (niezawierających grafów kompletnych / cyklicznych)?AAA Uwaga: Skonstruowanie grupy automorfizmów jest …
1
Podział krawędzi na tęczowe trójkąty
Zastanawiam się, czy następujący problem jest trudny NP. Wprowadź: prosty wykres i kolorowanie krawędzi ( nie weryfikuje żadnej konkretnej właściwości).G = ( V, E)G=(V,E)G = (V,E)fa: E→ { 1 , 2 , 3 }f:E→{1,2,3}f : E \to \{1,2,3\}faff Pytanie: czy można podzielić na trójkąty , tak aby każdy trójkąt miał …
2
Nazwij klasę wykresów: Rozłączne połączenie kliki i zbioru niezależnego
Pozwolić solsolG być wykresem będącym rozłącznym związkiem kliki i niezależnym zbiorem, tj. G =K.n1+K.n2)¯¯¯¯¯¯¯¯=K.n1+jan2).sol=K.n1+K.n2)¯=K.n1+jan2).G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . Klasa grafów wszystkich takich wykresów charakteryzuje się zabronionym indukowanym zestawem a zatem jest to przecięcie wykresu skupień i wykresu podziału (lub progu).H ={2K.2),P.3)}H.={2)K.2),P.3)}\mathcal{H} = \{2K_2, P_3\} Czy …
1
Kiedy wykres przyjmuje orientację, w której występuje co najwyżej jeden spacer?
Rozważ następujący problem: Dane wejściowe: prosty (niekierowany) wykres G = ( V, E)sol=(V.,mi)G=(V,E). Pytanie: Czy istnieje orientacja spełniająca właściwość, że dla każdego istnieje co najwyżej jeden (skierowany) - spacer?solsolGs , t ∈ V.s,t∈V.s,t \in Vsssttt Może to być równoważnie sformułowane jako: Dane wejściowe: prosty (niekierowany) wykres .G=(V,E)G=(V,E)G=(V,E) Pytanie: Czy istnieje …
1
Czy znana jest złożoność tego problemu?
Niech będzie wykresem. Zestaw wierzchołek nazywa krytyczna jeśli i nie wierzchołek w przylega dokładnie jeden wierzchołek w . Problemem jest znalezienie zbiór wierzchołków z co najmniej taką wielkość, że każdego niezbędny zestaw .G = ( V, E)G=(V,E)G=(V,E)X⊆ V.X⊆VX\subseteq VX≠ ∅X≠∅X\neq\emptysetV.∖ XV∖XV\setminus XXXXS.⊆ V.S⊆VS\subseteq VS.∩ X≠ ∅S∩X≠∅S\cap X\neq\emptysetXXX Problem ma następującą …
2
Zrozumienie graficznego mniejszego twierdzenia
To pytanie jest dwojakie i dotyczy głównie odniesienia: Czy jest gdzieś, gdzie podane są główne intuicje dowodzenia niewielkiego twierdzenia o grafie, bez zbytniego zagłębiania się w szczegóły? Wiem, że dowód jest długi i trudny, ale z pewnością muszą istnieć kluczowe pomysły, które można przekazać w łatwiejszy sposób. Czy istnieją inne …
2
Wyliczanie płaskich wykresów ograniczonej szerokości poprzecznej
Szukam odniesień do następującego problemu: biorąc pod uwagę liczby całkowite i , wyliczyć wszystkie nieizomorficzne wykresy płaskie na wierzchołkach i szerokości linii . Interesują mnie zarówno wyniki teoretyczne, jak i praktyczne, ale przede wszystkim praktyczne algorytmy, które można kodować i uruchamiać dla możliwie dużych wartości i (pomyśl i ). Jeśli …
2
Obliczanie przejściowego zakończenia / wyroku istnienia ścieżki
Było kilka pytań ( 1 , 2 , 3 ) na temat przechodniego uzupełniania, które zmusiły mnie do zastanowienia się, czy coś takiego jest możliwe: Załóżmy, że otrzymujemy wykres skierowany na dane wejściowe GsolG i chciałby odpowiedzieć na zapytania typu „(u,v)∈G+(u,v)∈sol+(u,v)\in G^+? ”, tzn. pytając, czy istnieje krawędź między dwoma …
2
Liczba cykli na wykresie
Ile cykli CkCkC_k (k≥3)(k≥3)(k \geq 3) znajdują się na wykresie wierzchołków, tak że wykres nie ma żadnego cyklu .nnn CmCmC_m (m>k)(m>k)(m>k) Na przykład , , wówczas wykres będzie miał najwyżej dwa , tak że nie będzie miał żadnegon=5n=5n=5k=3k=3k=3C3C3C_3GGGCk(k>3).Ck(k>3).C_k (k > 3). Myślę, że są O(n)O(n)O(n) cykle będą tam spełniające powyższe …
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.