Pytania otagowane jako graph-theory

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

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
Maksymalizacja sumarycznych wag krawędzi
Zastanawiam się, czy następujący problem ma nazwę lub wyniki z nim związane. Niech będzie wykresem ważonym, gdzie oznacza wagę krawędzi między i , a dla wszystkich , . Problem polega na znalezieniu podzbioru wierzchołków, który maksymalizuje sumę wag sąsiadujących z nimi krawędzi: Zauważ, że liczę krawędzie, które są wewnątrz podzbioru …
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
Testowanie właściwości dla niezależnych zestawów
Załóżmy, że otrzymaliśmy wykres GGG i parametry k,ϵk,ϵk,\epsilon. Czy istnieją zakresy wartości dlakkk (czy jest to wykonalne dla wszystkich kkk), dla których można sprawdzić, czy GGG jest ϵϵ\epsilon-dużo posiadania niezależnego zestawu przynajmniej wielkości kkk w samą porę O(n+poly(1/ϵ))O(n+poly(1/ϵ))O(n + \text{poly}(1/\epsilon)) ? Jeśli użyjemy zwykłego pojęcia ϵϵ\epsilon-dale (tj. co najwyżej ϵn2ϵn2\epsilon …
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.