Pytania otagowane jako graph-theory

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

1
Znalezienie optymalnej równoległości z ogólnego ważonego niekierowanego wykresu
Rozwiązuję problem „mieszania” zestawów nakładających się obrazów. Te zestawy mogą być reprezentowane przez niekierowany ważony wykres, taki jak ten: Każdy węzeł reprezentuje obraz. Nakładające się obrazy są połączone krawędzią. Ciężar krawędzi reprezentuje wielkość obszaru nakładania się ( wcześniejsze połączenie większego nakładania prowadzi do lepszej ogólnej jakości ). Algorytm ogólnie usuwa …
1
Zwiększenie wydajności w celu maksymalizacji minimalnego cięcia
Rozważ wykres ze wszystkimi krawędziami o pojemności jednostkowej. Można znaleźć min. Cięcie w czasie wielomianowym. Załóżmy, że mogę zwiększyć pojemność dowolnego kkkkrawędzie do nieskończoności (równoważne scalaniu węzłów po obu stronach krawędzi). Jaki jest optymalny sposób wyboru optymalnego zestawukkk krawędzie (których pojemność zostanie zwiększona do nieskończoności), aby zmaksymalizować minimalne cięcie?
1
Minimalne drzewo opinające dla wszystkich dopasowań wierzchołków
Natknąłem się na ten problem z dopasowaniem, dla którego nie jestem w stanie zapisać algorytmu czasu wielomianowego. Pozwolić P,QP,QP, Qbyć kompletnymi wykresami ważonymi z zestawami wierzchołków odpowiednio i , gdzie . Ponadto pozwalają i być funkcje ciężar na krawędziach i , odpowiednio.PVPVP_VQVQVQ_V|PV|=|QV|=n|PV|=|QV|=n|P_V| = |Q_V|=nwPwPw_PwQwQw_QPPPQQQ W przypadku modyfikujemy w następujący sposób: …
1
Jaka jest oczekiwana długość najkrótszej ścieżki hamiltonowskiej w losowo wybranych punktach z siatki planarnej?
kkk różnych punktów wybiera się losowo z siatki . (Oczywiście i jest daną stałą liczbą.) Na podstawie tych punktów budowany jest kompletny wykres ważony, tak że ciężar krawędzi między wierzchołkiem a wierzchołkiem jest równy odległości Manhattanu dwóch wierzchołków na pierwotnej siatce .p × qp×qp\times qk ≤ p × qk≤p×qk\leq p\times …
2
Problem ODD NAWET DELTA
Niech będzie wykresem. Niechbyć liczbą całkowitą. Niech będzie liczbą indukowanych przez krawędź posiadających wierzchołków i nieparzystą liczbę krawędzi. Niech będzie liczbą podgraphów indukowanych przez krawędź, mających wierzchołków i parzystą liczbę krawędzi. Niech . Problem ODD NAWET DELTA polega na obliczeniu , biorąc pod uwagę G i k .G = ( …
1
Sparametryzowana złożoność liczenia rowerów
W poprzednim pytaniu Sparametryzowany algorytm znajdowania biklików zapytałem, czy istnieją szybkie sparametryzowane algorytmy do znalezieniak×kk×kk\times k-biclique in an nnn wykres wierzchołków i dowiedziałem się, że był otwarty, jeśli jest FPT wrt kkk. To samo odnosi się do liczeniak×kk×kk\times k-bikiety, czy wiadomo, że to #W\[1\]W\[1\]W\[1\]-hard wrt kkk (lub jakieś inne pojęcie …
1
Czy para rozłącznych cykli homotopowych w podwójnym rozdziela wykres?
Pozwolić solGG być wykresem osadzonym na orientowanej, zwartej powierzchni rodzaju solggtak aby osadzanie było komórkowe. Rozważ podwójność wykresusol∗G∗G^*. Pozwolićdo1C1C_1 i do2)C2C_2 być rozłącznymi cyklami w sol∗G∗G^* które są homotopiczne względem siebie i niech mi1E1E_1 i mi2)E2E_2 być ich odpowiednimi zestawami krawędzi w solGGodpowiednio. JestG ∖ (mi1∪mi2))G∖(E1∪E2)G \setminus (E_1 \cup E_2) …
2
Złożoność znalezienia separatora grafów o danej właściwości
Czy są znane wyniki na temat złożoności znalezienia separatora (dowolnej wielkości) spełniającego daną właściwość? Wiem, że separator kliki jest łatwy do znalezienia (czas wielomianowy), a także wiem, że wiele artykułów rozważa problem znalezienia małych separatorów lub separatorów, które pozostawiają połączone komponenty wielkości co najwyżej ułamka wielkości oryginalnego wykresu. Ale co, …
3
Znajdowanie wszystkich cykli
Mam skończony zestaw S.SS, funkcja fa: S→ Sf:S→Sf:S\to Soraz całkowite zamówienie &lt;&lt;< na S.SS. Chcę znaleźć liczbę różnych cykliS.SS. Dla danego elementu s ∈ Ss∈Ss\in S Mogę użyć algorytmu Floyda (lub Brenta itp.), Aby znaleźć długość cyklu, w którym powtarzały się aplikacje faff wysyła sssdo; przy odrobinie wysiłku mogę zidentyfikować …
2
Czy mogę ograniczyć liczebność zbioru, jeśli wiadomo, że testowanie członkostwa w nim jest zakończone NP?
Chciałbym ograniczyć się do liczności zbioru grafów dysków jednostkowych N.NNwierzchołki. Wiadomo, że sprawdzenie, czy wykres należy do tego zestawu, jest trudne dla NP. Czy prowadzi to do jakiejkolwiek dolnej granicy liczności, zakładając, że P≠≠\neq NP? Załóżmy na przykład, że na wszystkich wykresach występuje kolejność N.NNwierzchołki. Czy twardość NP oznaczałaby wówczas, …
1
Osadzanie wykresu jako zbioru czworościanów rozłącznych wewnętrznie
Zdefiniuj siatkę w 3D jako połączoną kolekcję czworościanów z rozłącznymi wnętrzami (więc czworościany mają tylko k-face, k ≤ 2k≤2)k \le 2). Czy na podstawie dowolnego wykresu istnieje skuteczna procedura sprawdzania, czy można go osadzić jako siatkę? Osadzanie polega na odwzorowaniu wierzchołków wykresu na punkty w R3)R3)R^3 a krawędzie do linii …
2
Czy istnieją jakieś „graficzne” algebry, które mogą opisać „kształt” wykresów?
Jednym z głównych problemów w wyliczaniu wykresów jest określenie „kształtu” wykresu, np. Klasy izomorfizmu dowolnego konkretnego wykresu. Jestem w pełni świadomy, że każdy wykres może być reprezentowany jako macierz symetryczna. Jednak, aby uzyskać jego kształt, potrzebujesz kolekcji permutacji wierszy / kolumn, co czyni matrycę nieco mniej odpowiednią. Trudniej jest też …
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.