Próbuję zrozumieć niektóre pojęcia dotyczące rozkładu modułowego i wykresów szerokości kliki . W tym artykule („Na wykresach uporządkowanych za pomocą P4”) znajduje się dowód na to, jak rozwiązać problemy z optymalizacją, takie jak liczba kliki lub liczba chromatyczna za pomocą rozkładu...
W przypadku płaskiego osadzenia wykresu płaskiego na płaszczyźnie o prostych krawędziach, zdefiniuj wierzchołek jako ostry wierzchołek, jeśli maksymalny kąt między dwiema kolejnymi krawędziami wokół niego jest większy niż 180. Innymi słowy, jeśli istnieje linia przechodząca przez ten wierzchołek...
Jest to kontynuacja pytanie na ten temat nieskończonych wykresach. Odpowiedzi i komentarze do tego pytania zawierają listę obiektów i sytuacji, które są naturalnie modelowane przez nieskończone wykresy. Ale istnieją również liczne twierdzenia o grafach nieskończonych (patrz rozdział 8 w książce...
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do...
Wykresy płaskie są wolne od . Wykresy te mogą być rozłożone na części składowe tri połączone, które wiadomo, że są albo płaską lub K 5 składników.K.3 , 3K.3),3)K_{3,3}K.5K.5K_5 Czy istnieje taki „ładny” rozkład grafów z rodzaju 1? W swojej przełomowej pracy nad nieletnimi grafami Roberston i...
Mniej więcej rok temu razem z przyjacielem zastanawialiśmy się, jak zaimplementować algorytm Kruskala dla gęstych wykresów w lepszej niż zwykle granicy O ( m logm )O(mlogm)O(m \log m) (bez zakładania wstępnie posortowanych krawędzi). Konkretnie, osiągamy Θ ( n2))Θ(n2))\Theta(n^2) we wszystkich...
1-wym algorytm Weisfeiler-Lehman (WL) jest powszechnie znany jako kanonicznej oznakowania lub algorytmu kolor rafinacji. Działa w następujący sposób: Początkowe zabarwienie jest jednolite, C 0 ( v ) = 1 dla wszystkich wierzchołków v ∈ V ( G ) ∪ V ( H ) .do0do0C_0do0( v ) = 1do0(v)=1C_0(v) = 1v ∈...
Uważamy DAG (skierowane wykresy acykliczne) z jednym węzłem źródłowym jeden docelowego węzła ; dozwolone są równoległe krawędzie łączące tę samą parę wierzchołków. - cięcie jest zestaw krawędzi, których usunięcie usunięcie wszystkich - ścieżek dłuższe niż ; krótsze - szlaki, a także wydłużone...
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!)....
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...
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...
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...
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b -> b seq ⊥ b =...
Najdłuższy problem ze ścieżką to trudność NP. (Typowy?) Dowód polega na zmniejszeniu problemu ścieżki hamiltonowskiej (która jest NP-zupełna). Zauważ, że tutaj ścieżka jest uważana za (węzłową) prostą. Oznacza to, że żaden wierzchołek nie może wystąpić więcej niż jeden raz na ścieżce. Oczywiście...
Czy jest coś znanego na temat następującego problemu? Czy to w ogóle ma sens? Jak to jest nazywane? Czy jest to banalnie równoważne z jakimś innym problemem? Jaka jest złożoność czasu? Biorąc pod uwagę nieukierowany (ogólny / płaski / ograniczony / itd.) Wykres G = (V, E), znajdź maksymalny...
G=(V,E)G=(V,E)G=(V,E)minS⊂V e(S,Sc)min(|S|,|Sc|),minS⊂V e(S,Sc)min(|S|,|Sc|),\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},e(S,Sc)e(S,Sc)e(S,S^c)SSSScScS^c Bardziej konkretnie przypuszczać wiem średnica wynosi co najmniej (albo co najwyżej) . Co to mówi mi o przewodności, jeśli w ogóle? I...
Załóżmy, że łączymy punkty za pomocą zestawu niekierowanych krawędzi E tak, że albo ( i , j ) jest podłączony do ( i + 1 , j + 1 ) , albo ( i + 1 , j ) jest podłączony do ( i , j + 1 ) , niezależnie i równomiernie losowo dla wszystkich i , j .V=Z2V=Z2V = \mathbb{Z}^2EEE(i,j)(i,j)(i,...
Zarówno GI, jak i Knot Problem stanowią problem decydowania o równoważności strukturalnej obiektów matematycznych. Czy są jakieś wyniki ustanawiające powiązania między nimi? Ładne powiązania problemu węzłów z fizyką statystyczną zostały zbadane za pomocą wielomianów węzłów , czy istnieją podobne...
Interesują mnie wykresy nnn wierzchołków, które można wytworzyć w następujący sposób. Zacznij od dowolnego wykresu GsolG na k≤nk≤nk\le n wierzchołków. Oznacz wszystkie wierzchołki w GsolG jako nieużywane . Opracowanie nowego wykres dodaje się nowy wierzchołek V , który jest połączony z jedną lub...
To pytanie jest związane z jednym z moich wcześniejszych pytań, trudnymi NP na drzewach . Szukam problemów, które są kompletne P na