Pytania otagowane jako graph-theory

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

1
Czułość właściwości wykresu
W [1] Turan pokazuje, że czułość (zwana w dokumencie „złożonością krytyczną”) właściwości wykresu jest ściśle większa niż ⌊ 14m ⌋⌊14m⌋\lfloor {1\over 4} m \rfloorgdziemmmjest liczbą wierzchołków na wykresie. Dalej zakłada, że ​​każda nietrywialna właściwość graficzna ma czułość≥m−1≥m-1\geq m-1. Wspomina, że ​​zostało to zweryfikowane dla. Czy poczyniono jakieś postępy w tej …
1
Podziel wykres na cykle rozłączne węzłów
Powiązany problem: Twierdzenie Veblena stwierdza, że ​​„Wykres dopuszcza rozkład cyklu wtedy i tylko wtedy, gdy jest on parzysty”. Cykle są rozłączne na krawędziach, ale niekoniecznie są rozłączne w węzłach. Innymi słowy: „Zestaw krawędzi wykresu można podzielić na cykle, jeśli i tylko wtedy, gdy każdy wierzchołek ma równy stopień”. Mój problem: …
2
Biorąc pod uwagę 4-cyklowy wykres , czy możemy ustalić, czy ma on 3-cykl w czasie kwadratowym?
Problem z rowem jest następujący:kkk Instancja: Niekierowany wykres z wierzchołkami i do n \ wybierz 2 krawędzie.nsolsolGnnn( n2))(n2))n \choose 2 Pytanie: Czy w G istnieje (właściwy) cykl K ?kkksolsolG Tło: Dla każdego ustalonego kkk możemy rozwiązać cykl 2 tys2)k2k w czasie O ( n2))O(n2))O(n^2) . Raphael Yuster, Uri Zwick: Znalezienie …
1
Czy ta gęsta wersja algorytmu Kruskala jest dobrze znana?
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(mlog⁡m)O(m \log m) (bez zakładania wstępnie posortowanych krawędzi). Konkretnie, osiągamy Θ ( n2))Θ(n2))\Theta(n^2) we wszystkich przypadkach, podobnie jak Prim, gdy implementujemy je za pomocą macierzy …
1
Co możemy udowodnić za pomocą nieskończonych wykresów, że bez nich nie możemy udowodnić?
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 Diestela), z których na przykład bardzo popularny jest nieskończony lemat …
1
Rysujesz wykresy z kilkoma „ostrymi” wierzchołkami?
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 wierzchołek w osadzeniu, tak że wszystkie krawędzie padające na ten wierzchołek leżą …
1
Rozkład grafów połączonych na k na elementy połączone (k + 1)
Połączony wykres można rozłożyć na jego połączone elementy. To drzewo punktów odcięcia bloku jest unikalne. Podobnie, dwupołączone wykresy można rozłożyć na trójkołowe komponenty. Odpowiednie drzewo SPQR opisuje wszystkie cięcia 2-wierzchołkowe na wykresie i jest jednoznacznie określone na podstawie jego wykresu. Ten proces nie uogólnia się na większą łączność. Na przykład, …
1
Utrzymanie porządku na liście w w Czas
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 elementu usuwa go z listy minPointer: biorąc pod …
1
Modułowy rozkład i szerokość kliki
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 modułowego. Rozwiązanie tych problemów przez skomponowanie (przy użyciu sumy …
3
Złożoność kolorowania krawędzi na wykresach płaskich
3 krawędzi barwienia wykresów sześcienny -Complete. Twierdzenie o czterech kolorach jest równoważne z tym, że „Każdy sześcienny płaski wykres bez mostka ma 3 krawędzie do pokolorowania”.N.P.N.P.NP Jaka jest złożoność 3-krawędziowego kolorowania sześciennych wykresów płaskich? Ponadto, przypuszcza się, że -edge barwiący N P -hard dla płaskich wykresów z maksymalnym stopniu hemibursztynianu …
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.