Pytania otagowane jako graph-theory

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

3
Dokładne rozwiązywanie superstrun
Co wiadomo o dokładnej złożoności najkrótszego problemu superstrun? Czy można to rozwiązać szybciej niż O∗(2n)O∗(2n)O^*(2^n) ? Czy znane są algorytmy, które rozwiązują najkrótszy superstrun bez redukcji do TSP? UPD: O∗(⋅)O∗(⋅)O^*(\cdot) tłumi czynniki wielomianowe. Najkrótszy problem superstrun to problem, którego odpowiedzią jest najkrótszy ciąg, który zawiera każdy ciąg z danego zestawu …
1
Czy dominujący problem z zestawem jest ograniczony do płaskich dwustronnych grafów o maksymalnym stopniu NP-3?
Czy ktoś wie o wyniku NP-kompletności dla problemu ZESTAW DOMINUJĄCY na wykresach, ograniczonego do klasy płaskich dwustronnych grafów o maksymalnym stopniu 3? Wiem, że jest NP-kompletny dla klasy grafów płaskich o maksymalnym stopniu 3 (patrz książka Gareya i Johnsona), a także dla grafów dwustronnych o maksymalnym stopniu 3 (patrz M. …
2
Klasy wykresów, w których problemy cyklu Hamiltoniana i ścieżki Hamiltoniana mają różną złożoność
Podczas przeszukiwania Systemu informacji o klasach grafów i ich inkluzjach znalazłem kilka klas grafów, dla których problem cyklu Hamiltoniana jest NP-kompletny, natomiast złożoność problemów ścieżki Hamiltonian NIE jest znana. Niektóre z tych klas to dwuczęściowe wykresy o maksymalnym stopniu 3, wykresy o maksymalnym stopniu 3 i 2 połączone sześcienne wykresy …
2
Delikatne wprowadzenie do izomorfizmu grafów dla grafów o ograniczonej wartościowości
Czytam o klasach grafów, dla których izomorfizm grafów ( ) jest . Jednym z takich przypadków są wykresy ograniczonej wartościowości (maksimum nad stopniem każdego wierzchołka), jak wyjaśniono tutaj . Ale uznałem to za zbyt abstrakcyjne. Byłbym wdzięczny, gdyby ktokolwiek mógł zasugerować mi referencje o charakterze ekspozycyjnym. Nie mam silnego doświadczenia …
2
Zakazane nieletnie dla ograniczonych wykresów szerokości
To pytanie jest podobne do jednego z moich poprzednich pytań. Wiadomo, że jest niedozwolonym pomniejszeniem dla wykresów szerokości co najwyżej .Kt+2Kt+2K_{t+2}ttt Czy istnieje ładnie skonstruowana, sparametryzowana, nieskończona rodzina wykresów (innych niż pełne wykresy i wykresy siatki), które są minimalnie zabronionymi nieletnimi dla wykresów o każdej szerokości. Innymi słowy, czy istnieje …
2
Czas pokrycia kierowanych wykresów
Biorąc pod uwagę losowy spacer na wykresie, czas pokrycia jest pierwszym (oczekiwana liczba kroków), że każdy wierzchołek został trafiony (pokryty) przez spacer. W przypadku podłączonych niekierowanych wykresów czas pokrycia jest znany z górnej granicy . Istnieją silnie połączone digrafy z wykładniczym czasem pokrycia w n . Przykładem tego jest dwuznakiem …
1
Zestawy stopni dla liniowych wykresów rozszerzenia
Liniowe rozszerzenie L.L.L z poset P.P.\mathcal{P} jest liniowy porządek na elementach P.P.\mathcal{P} tak, że x ≤ yx≤yx \leq y w implikuje w dla wszystkich . x ≤ y L x , y ∈ PP.P.\mathcal{P}x ≤ yx≤yx \leq yL.L.Lx , y∈ P.x,y∈P.x,y\in\mathcal{P} Liniowy wykres przedłużenie jest wykresem na zestawie liniowe przedłużenie …
3
Właściwości losowo ukierunkowanych wykresów z ustalonym kątem końcowym
Interesują mnie właściwości losowo ukierunkowanych wykresów o ustalonym out-stopniu ddd . Wyobrażam sobie losowy model wykresu, w którym każdy wierzchołek wybiera u sąsiadów (powiedzmy z zamiennikiem) Pytanie : Czy coś wiadomo o rozkładzie stacjonarnym i czasach mieszania losowych spacerów na tych losowych grafach (dla różnych wartości )? ddd Szczególnie interesuje …
1
Szybkie mieszanie łańcuchów Markowa na 3-kolorowych cyklach
Dynamika Glaubera to łańcuch Markowa na kolorach wykresu, w którym na każdym kroku próbuje się pokolorować losowo wybrany wierzchołek o losowym kolorze. Nie miesza się w przypadku 3 kolorów w 5 cyklach: istnieje 30 3 kolorów, ale tylko 15 z nich można osiągnąć za pomocą etapów kolorowania pojedynczego wierzchołka. Mówiąc …
2
Problem cięcia bez H
Załóżmy, że otrzymałeś połączony, prosty, niekierowany wykres H. Problem cięcia bez H jest zdefiniowany następująco: Biorąc pod uwagę prosty, nieukierowany wykres G, istnieje cięcie (podział wierzchołków na dwa niepuste zbiory, L, R), tak że oba wykresy indukowane przez zestawy cięcia (L i R) nie zawierają izomorficznego subgrafu do H . …
1
Zabronione osoby niepełnoletnie w przypadku związanych z nimi wykresów rodzajów
Powszechnie wiadomo, że i K 3 , 3 są niedozwolone w przypadku wykresów planarnych. Istnieją setki zakazanych nieletnich dla wykresów osadzanych na torusie. Liczba niedozwolonych nieletnich dla wykresów osadzanych na powierzchni rodzaju g jest funkcją wykładniczą g . Moje pytanie brzmi:K5K5K_5K3,3K3,3K_{3,3} Ma wyraźnego wykresem o t wierzchołków (co nie jest …
1
Jaka jest złożoność tego problemu z grafem?
Biorąc pod uwagę prosty niekierowany wykres GGG , znajdź podzbiór A≠∅A≠∅A\neq \emptyset wierzchołków, taki jak dla dowolnego wierzchołka x∈Ax∈Ax\in A co najmniej połowa sąsiadów xxx również znajduje się w AAA i rozmiar AAA jest minimalny. Oznacza to, że szukamy gromady, w której co najmniej połowa sąsiedztwa każdego wewnętrznego wierzchołka pozostaje …
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.