Pytania otagowane jako graph-theory

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

1
Złożoność dominującego problemu w określonych podklasach wykresów akordowych
Interesuje mnie złożoność problemu dominującego zestawu (DSP) w niektórych określonych klasach grafów, które są podklasami grafów akordowych . Wykres jest nieukierowanym wykresem ścieżki, jeśli jest to wykres przecięcia wierzchołków rodziny ścieżek w jakimś niekierowanym drzewie. Niech UP będzie klasą niekierowanych grafów ścieżek. Wykres jest grafem EPT, jeśli jest to wykres …
2
Zdecentralizowany algorytm do określania wpływowych węzłów w sieciach społecznościowych
W tym artykule Kempe-Kleinberg-Tardos autorzy proponują zachłanne algorytmy oparte na funkcjach submodularnych w celu określenia najbardziej wpływowych węzłów na wykresie, z zastosowaniem do sieci społecznościowych.kkk Zasadniczo algorytm wygląda następująco: S=empty setS=empty setS = {\rm empty~set} wybierz węzeł o najwyższym indywidualnym wpływie, nazwij go ; S = S ∪ v 1v1v1v_1S=S∪v1S=S∪v1S …
1
Algorytmy równoległe dla osiągalności w ukierunkowanych grafach płaskich
Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie pomocą procesorów O ( m + n ) .O(logn)O(logn)O({\log}n)O(m+n)O(m+n)O(m+n) Jaki jest najbardziej znany algorytm równoległy dla łączności st w ukierunkowanych grafach płaskich? Podaj czas działania, deterministyczny / losowy algorytm i zastosowany model PRAM (zakładając, …
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 …
1
Czy „Czy permutacja jest automorfizmem grafu w moim zestawie?” NP-kompletny?
Załóżmy, że mamy zestaw S grafów (wykresy skończone, ale ich nieskończona liczba) i grupę P permutacji, która działa na S. Instancja: permutacja pw P. Pytanie: Czy istnieje wykres g w S, który dopuszcza automorfizm p? Czy ten problem NP-zupełny dla niektórych zestawów S? Łatwo byłoby sprawdzić, czy wykres dopuszcza permutację …
1
Jaka jest prawidłowa definicja drzewa
Jak mówi tytuł, jaka jest poprawna definicja drzewa ? Istnieje kilka artykułów, które mówią o drzewach K i drzewach częściowych K jako alternatywnych definicjach dla wykresów o ograniczonej szerokości i widziałem wiele z pozornie niepoprawnych definicji. Na przykład co najmniej jedno miejsce definiuje drzewa- K w następujący sposób:kkkkkkkkkkkk Wykres nazywa …
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 …
1
Liczba 4 cykli
Niech C4C4C_4 będzie cyklem z czterema wierzchołkami. Aby uzyskać dowolny wykres GGG z nnn wierzchołkami i krawędziami m, powiedz m>nn−−√m>nnm>n\sqrt n , ileistniejeC4C4C_4? Czy jest na to dolna granica?
1
Czy szerokość sugeruje istnienie nieletniego ?
Niech zostanie naprawione, a będzie (połączonym) wykresem. Jeśli się nie mylę, z pracy Bodlaendera [1, Twierdzenie 3.11] wynika, że ​​jeśli szerokość wynosi w przybliżeniu co najmniej , wówczas zawiera gwiazdę jako pomniejszą.G G 2 k 3 G K 1 , kkkksolGGsolGG2 tys3)2k32k^3solGGK.1 , kK1,kK_{1,k} Czy możemy zmniejszyć termin ? To …
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.