Graf decydujący Homomorfizm jest ogólnie NP-Complete. Czy istnieją wyniki, które badają ten problem, gdy leżące u podstaw wykresy mają strukturę algebraiczną (takie jak decydowanie o homomorfizmach z wykresów Coseleya lub Cayleya do innych wykresów o określonej strukturze również)? Oprócz wyników...
Czy istnieje znana konstrukcja kodu korygującego błędy liniowe (z rozsądnymi parametrami), na przykład gdy podano logiczny wektor zwraca również wartość logiczną wektora logicznego? (chociaż to koniec \ mathbb {F} _q )ECC:Fnq→FmqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to...
Niech . Muszę wygenerować proste wykresy obwodu tak aby zestaw wszystkich motocykli tworzy podwójną osłonę (to znaczy, każda krawędź jest dzielona przez dokładnie dwa motocykle) i takie, że przecięcie dowolnych dwóch motocykle to albo wierzchołek, krawędź, albo pusty. Wygenerowane wykresy powinny...
Biorąc pod uwagę rodzinę najwyżej n podzbiorów { 1 , 2 , … , n } . Zamknięcie związek C jest inny zestaw rodziny C zawierający każdy zestaw, które mogą być skonstruowane poprzez związek 1 lub więcej grup w F . Przez | C | oznaczymy liczbę zestawów w C .faF\mathcal Fnnn{ 1 , 2 , … , n }{1,2,…,n}\{...
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ )...
Jako kontynuacja mojego poprzedniego pytania , które rozwiązał Hsien-Chih Chang, oto kolejna próba znalezienia odpowiedniego uogólnienia twierdzenia Ramseya. (Nie musisz czytać poprzedniego pytania; ten post jest samodzielny.) Parametry: podane są liczby całkowite , a następnie jest wybierane...
Twierdzenie Fáry'ego mówi, że prosty wykres płaski można narysować bez przecięć, tak że każda krawędź jest odcinkiem linii prostej. Moje pytanie brzmi, czy istnieje analogiczne twierdzenie dla grafów ograniczonej liczby skrzyżowań . W szczególności, czy możemy powiedzieć, że można narysować prosty...
Mam wykres solGGktóry składa się tylko z wykresów gwiazd. Wykres gwiezdny składa się z jednego centralnego węzła mającego krawędzie do każdego innego węzła w nim. PozwolićH.1,H.2), ... ,H.nH1,H2,…,HnH_1, H_2, \ldots, H_n być różnymi wykresami gwiazd o różnych rozmiarach, które są obecne w solGG....
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...
EDYTOWANO, ABY DODAĆ : Na to pytanie zasadniczo udzielono odpowiedzi; zobacz ten wpis na blogu, aby uzyskać więcej informacji. Dziękujemy wszystkim, którzy opublikowali tutaj komentarze i odpowiedzi. PYTANIE ORYGINALNE Jest to, mam nadzieję, mądrzejsza i lepiej poinformowana wersja pytania,...
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...
Załóżmy, że mamy do wykresu na węzłów. Chcielibyśmy przypisać do każdego węzła lub . Nazwij to konfiguracją . Liczba s, które musimy przypisać, to dokładnie (stąd liczba s to .) Biorąc pod uwagę konfiguracji , patrzymy na każdy węzeł i sumujemy wartości przypisane jego sąsiadom, wywołanie to ....
Edycja: teraz jest pytanie uzupełniające związane z tym postem. Definicje Niech i będą liczbami całkowitymi. Używamy notacji .ccckkk[i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\} macierzy mówi się -to- barwiących matrycy , jeśli zachodzi:c×cc×cc \times cM=(mi,j)M=(mi,j)M =...
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 ×...
Prowadzę kurs meta-heurystyki i muszę wygenerować ciekawe przykłady klasycznych problemów kombinatorycznych dla projektu semestralnego. Skupmy się na TSP. Zajmujemy się wykresami wymiarów200200200i większe. Próbowałem oczywiście wygenerować wykres z macierzą kosztów z wartościami pobranymi z...
Jestem studentką z Indii. Jestem bardzo zainteresowany uczestnictwem w warsztatach, konferencjach i zaproszonych wykładowcach prowadzonych przez wybitnych profesorów. Pod koniec rozmowy jak zwykle niektóre osoby będą zadawać pytania, a mówca na nie odpowie. Ale moim problemem jest to, że nie...
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...
Powiedzmy, że mamy funkcję boolowską fa: { - 1 , 1}n→ { - 1 , 1 }f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} i aplikujemy δδ\delta-losowe ograniczenie na faff. Ponadto powiedz, że drzewo decyzyjneT.TT to oblicza faff zmniejsza się O ( 1 )O(1)O(1)w wyniku losowego ograniczenia. Czy to implikuje...
Niech będzie wykresem. Zestaw wierzchołek nazywa krytyczna jeśli i nie wierzchołek w przylega dokładnie jeden wierzchołek w . Problemem jest znalezienie zbiór wierzchołków z co najmniej taką wielkość, że każdego niezbędny zestaw .G = ( V, E)G=(V,E)G=(V,E)X⊆ V.X⊆VX\subseteq VX≠ ∅X≠∅X\neq\emptysetV.∖...
Niech i będą dwoma połączonymi wykresami regularnymi o rozmiarze . Niech być zbiorem permutacji tak, że . Jeśli następnie jest zestaw automorfizmy o .GGGHHHrrrnnnAAAPPPPGP−1=HPGP−1=HPGP^{-1}=HG=HG=HG=HAAAGGG Jaka jest najbardziej znana górna granica rozmiaru ? Czy są jakieś wyniki dla...