Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

1
Dokładny algorytm dla problemu znakowania krawędzi w DAG
Wdrażam część systemu, która wymaga pomocy. Dlatego kadruję go jako problem graficzny, aby uczynić go niezależnym od domeny. Problem: Otrzymujemy ukierunkowany wykres acykliczny . Bez utraty ogólności załóżmy, że G ma dokładnie jeden wierzchołek źródłowy s i dokładnie jeden wierzchołek tonący ; pozwolić P oznacza zbiór wszystkich skierowanych ścieżek z …
1
Idealne dopasowania na szachownicy?
Zastanów się nad problemem znalezienia maksymalnej liczby rycerzy, którzy mogą zostać postawieni na szachownicy bez atakowania się dwóch z nich. Odpowiedź brzmi 32: nie jest zbyt trudno znaleźć idealne dopasowanie (wykres wywołany ruchami rycerza jest dwustronny, i istnieje idealne dopasowanie dla planszy 4 × 4), co jest oczywiście minimalną osłoną …
2
Liczba triangulacji zbioru
Po tym, jak tego lata Emo Welzl przemawia na ten temat, wiem, że liczba triangulacji zbioru punktów na płaszczyźnie wynosi między około Ω ( 8,48 n ) a O ( 30 n ) . Przepraszam, jeśli jestem nieaktualny; aktualizacje mile widziane.nnnΩ ( 8,48n)Ω(8.48n)\Omega(8.48^n)O ( 30n)O(30n)O(30^n) Wspomniałem o tym na zajęciach …
1
Przewodnictwo i średnica na zwykłych wykresach
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 odwrotnie, przypuśćmy, że wiem, że przewodnictwo wynosi co najmniej (lub przynajmniej) . Co to mówi mi o średnicy, jeśli w ogóle?DDDαα\alpha
2
Liczba minut wykresu bez użycia algorytmu Kargera
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 z zestawu skrótów do innego zestawu liczności ( n2))(n2))n \choose …
1
Pojemność jednoznacznie rozwiązanej układanki (USP)
W swoim kluczowym artykule Teoretyczne algorytmy grupowania macierzy Cohn, Kleinberg, Szegedy i Umans przedstawiają koncepcję unikatowej układanki (zdefiniowanej poniżej) i zdolności USP. Twierdzą oni, że Coppersmith i Winograd, w ich własnym papierze przełomowy Mnożenie macierzy poprzez ciąg arytmetyczny , „pośrednio” udowodnić, że zdolność USP jest 3/22/33/22/33/2^{2/3} . Twierdzenie to zostało …
2
Zastosowanie liczb Ramseya
Definicja liczb Ramseya jest następująca: Niech jest dodatnią liczbą taką, że każdy wykres zamówienia na przynajmniej R ( , b ) obejmuje albo klika w ciągu wierzchołków lub zestaw się na stałym b wierzchołków.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Pracuję nad jakimś rozszerzeniem Ramsey Numbers. Chociaż badanie ma pewne teoretyczne zainteresowania, ważne byłoby poznanie motywacji …
3
Gra Dracula
Kontekst To pytanie jest motywowane grą planszową o nazwie „Dracula”. W tej grze jest jeden wampir i czterech łowców, których celem jest złapanie wampira. Gra toczy się w Europie. Gra wygląda następująco: 1. Łowca umieszcza wszystkich łowców w miastach. W tym samym mieście można umieścić więcej niż jednego myśliwego. 2. …
4
Relaksacja LP niezależnego zestawu
Próbowałem następującej relaksacji LP maksymalnie niezależnego zestawu max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 Dostaję 1/21/21/2 za każdą zmienną za każdy sześcienny dwudzielny wykres, który próbowałem. Czy to prawda dla wszystkich połączonych sześciennych dwudzielnych grafów? Czy istnieje relaksacja LP, która działa lepiej …
4
Odnośnie do metod Pfaffa w liczeniu i kombinatoryce
Ostatnio zastanawiałem się nad wprowadzeniem do algorytmów holograficznych. Natknąłem się na obiekty kombinatoryczne zwane Pfaffians. W tej chwili tak naprawdę niewiele o nich wiem i natknąłem się na zaskakujące zastosowania, które można zastosować. Na przykład dowiedziałem się, że można ich używać do skutecznego liczenia liczby idealnych dopasowań na wykresach płaskich. …
1
Twierdzenie Ramseya dla zbiorów zbiorów
Podczas eksploracji różnych technik dowodzenia dolnych granic dla algorytmów rozproszonych przyszło mi do głowy, że następujący wariant twierdzenia Ramseya może mieć zastosowania - jeśli to prawda. Podano parametry: kkk , KKK , nnn , a następnie wybrano NNN aby było wystarczająco duże. Terminologia: podzbiór mmm jest podzbiorem rozmiaru mmm . …
2
Partycja wolna od H.
To jest pytanie, zainspirowany problemu cięcia H-darmo . Biorąc pod uwagę wykres, podział jego zbioru wierzchołków na r części V 1 , V 2 , … , V r jest wolny od H, jeśli G [ V i ] nie indukuje kopii H dla wszystkich i , 1 ≤ i …
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.