Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

1
Czy znana jest złożoność tego problemu?
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.∖ XV∖XV\setminus XXXXS.⊆ V.S⊆VS\subseteq VS.∩ X≠ ∅S∩X≠∅S\cap X\neq\emptysetXXX Problem ma następującą …
1
Losowe ograniczenia i związek z całkowitym wpływem funkcji boolowskich
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 tofafaf ma bardzo niski wpływ całkowity?
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
Zrozumienie przemówień na konferencjach i warsztatach
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 rozumiem większości pytań i odpowiedzi. Nawet jeśli zadam jakieś pytanie, …
2
Generowanie interesujących problemów optymalizacji kombinatorycznej
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 losowegoU( 0 , 1 )U(0,1)U(0,1)i odkrył, że (zgodnie z oczekiwaniami) histogram kosztu ścieżki (sporządzony przez próbkowanie …
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
Istnienie „matryc do barwienia”
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 = (m_{i,j})ccckkk mamy dla wszystkich ,mi,j∈[k]mi,j∈[k]m_{i,j} \in [k]i,j∈[c]i,j∈[c]i, j \in [c] dla wszystkich z i mamy .i,j,ℓ∈[c]i,j,ℓ∈[c]i,j,\ell \in [c]i≠ji≠ji …
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) …
3
Ile słów długości
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, które zadałem na MathOverflow. Kiedy zadałem to pytanie, nie znałem nawet …
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ż …
1
Ograniczanie liczby krawędzi między wykresami gwiazdowymi, tak że wykres jest płaski
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. Nazywamy zbiór wszystkich węzłów, które są centrami …
2
Rysowanie wykresów ograniczonej liczby skrzyżowań
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 wykres z liczbą przecięcia k, aby na rysunku było …
2
Rozszerzenia twierdzenia Ramseya: monochromatyczne, ale różnorodne
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 jako wystarczająco duże. Terminologia: podzbiór jest podzbiorem rozmiaru .1≪d≪k≪n1≪d≪k≪n1 \ll d \ll k …
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.