Płaska wykres przedstawia wykres, który może być osadzony w płaszczyźnie, bez konieczności przekraczania krawędzie. Niech będzie - jednolitym hipergraphem, tj. Hipergraphem takim, że wszystkie jego hipergezy mają rozmiar k.kG = ( X, E)G=(X,E)G=(X,E)kkk Wykonano już pewne prace związane z...
Chcę być bardzo konkretny. Czy ktoś wie o odrzuceniu lub dowodzie następującej propozycji: ∃ p ∈ Z [ x ] , n , k , C∈ N ,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀ G , H∈ S.T.R Udo[ Σsolr a p h] ( m i n ( | G | , | H| )=n,G≄H)...
Biorąc pod uwagę ukierunkowany wykres z n węzłami, tak że każdy wierzchołek ma dokładnie dwie krawędzie wychodzące, a liczbę naturalną N zakodowaną dwójkowo, dwa wierzchołki s i t, Chcę policzyć liczbę (niekoniecznie prostych) ścieżek od s do t w obrębie N kroków. Czy to trudny problem # P? Lub...
Wiemy np. Z Koutis-Miller-Peng (na podstawie pracy Spielmana i Tenga), że możemy bardzo szybko rozwiązać układy liniowe dla macierzy które są wykresem macierzy Laplaciana dla niektórych rzadkich wykresów z nieujemnymi wagami krawędzi .Ax=bAx=bA x = bAAA Teraz (pierwsze pytanie) rozważ użycie...
Niech C4C4C_4 będzie cyklem z czterema wierzchołkami. Aby uzyskać dowolny wykres GGG z nnn wierzchołkami i krawędziami m, powiedz m>nn−−√m>nnm>n\sqrt n , ileistniejeC4C4C_4? Czy jest na to dolna
Tutaj: http://www.planarity.org/Klein_elementary_graph_theory.pdf (w osadzeniach rozdziałów) podano definicję kombinatorycznego osadzania wykresu płaskiego. (z definicją ścian i tak dalej) Choć można go łatwo zastosować do dowolnego wykresu, definiują wykres płaski jako wykres, dla którego...
Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai...
Jest sformułowany przez rozszerzenie wykresów progowych . Biorąc pod uwagę wykres progowy gdzie jest kliką, a jest niezależnym zbiorem, moje rozszerzenie jest następujące: Każdy wierzchołek można zastąpić nową kliką tak, że wierzchołki mają to samo sąsiedzi .( C, Ja)(do,ja)(C,I)dodoCjajaIv ∈...
W słynnym kontrprzykładzie dla izomorfizmu grafów metodą Weisfeiler-Lehman (WL) następujący gadżet został skonstruowany w tym artykule przez Cai, Furer i Immerman. Konstruują wykres podany przezXk= ( Vk, Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) V.k= Ak∪ B.k∪ M.k gdzie ZAk= { aja∣ 1 ≤ i ≤ k } ,bk= { bja∣ 1 ≤...
Powiedzmy, że rodzina grafów ma długo indukowane ścieżki, jeśli istnieje stała ϵ > 0, tak że każdy wykres G w F zawiera ścieżkę indukowaną na | V ( G ) | ϵ wierzchołki. Interesują mnie właściwości rodzin grafów, które zapewniają istnienie długo indukowanych ścieżek. W szczególności zastanawiam...
Na wykresie niezależny zestaw jest podzbiorem wierzchołków, który nie zawiera krawędzi jako indukowanego podsgrafu. Problem znajdowania największych niezależnych zestawów na wykresie jest fundamentalnym zagadnieniem algorytmicznym i trudnym. Rozważmy bardziej ogólne pytanie dotyczące znalezienia...
To może brzmieć bardziej jak pytanie z nauk społecznych niż TCS, ale tak nie jest. Czytając „ Randomizowane algorytmy ” opisujące problem stabilnego małżeństwa, można przeczytać następujące informacje (str. 54) „Można wykazać, że dla każdego wyboru list preferencji istnieje co najmniej jedno...
To mnie dezorientuje. Jednym z łatwych przypadków liczenia jest sytuacja, gdy problem decyzyjny występuje w i nie ma rozwiązań.PPP Wykład pokazuje, że problem zliczania liczby idealnych dopasowań na grafie dwustronnym (równoważnie, zliczanie liczby okładek cykli na ukierunkowanym wykresie) jest...
Skrzyżowane z MO . Niech CCC będzie klasą grafu zdefiniowaną przez skończoną liczbę zabronionych indukowanych podrożników, z których wszystkie są cykliczne (zawierają co najmniej jeden cykl). Czy istnieją problemy związane z grafem trudnym dla NP, które można rozwiązać w czasie wielomianowym...
Chciałbym zapytać, czy jest na to już opublikowany wynik: Bierzemy wszystkie możliwe różne ścieżki między każdą parą węzłów dwóch połączonych regularnych (o powiedzmy stopnia , i liczby węzłów ) wykresów i zapisujemy ich długości. Oczywiście ta liczba odrębnych ścieżek ma charakter wykładniczy....
Chciałbym wiedzieć, czy w (niedeterministyczny obszar logów) można rozstrzygnąć następujący problem :N L.NL\mathsf{NL} Biorąc pod uwagę ukierunkowany wykres z dwoma wyróżnionymi wierzchołkami s i t , czy istnieje unikalna ścieżka od s do t w G ?solGGssstttssstttsolGG Czuję, że to może być w...
Załóżmy, że mamy półgrupę z elementami . Naszym celem jest obliczanie produktów .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j W swoim artykule „Optymalne przetwarzanie wstępne dla odpowiedzi na...
Twierdzenie Courcelle'a stwierdza, że każdą właściwość grafu definiowaną w monadycznej logice drugiego rzędu można rozstrzygać w czasie liniowym na wykresach ograniczonej szerokości . Jest to jedno z najbardziej znanych algorytmicznych meta-twierdzeń. Zmotywowany twierdzeniem Courcelle,...
Co obecnie wiadomo na temat zbliżenia problemu rodzaju? Wstępne wyszukiwanie mówi mi, że stałe przybliżenie współczynnika jest trywialne dla wystarczająco gęstych wykresów, a algorytm aproksymacji został wykluczony. Czy te informacje są aktualne, czy są znane lepsze
Rozluźnijmy trochę kolorystykę, tzn. Pozwalamy niewielkiej liczbie sąsiadujących wierzchołków na przypisanie tego samego koloru. Składnik monochromatyczny jest zdefiniowany jako składnik połączony w podsgrafie wywołany przez zestaw wierzchołków, które otrzymują ten sam kolor, a pytanie polega na...