Ograniczanie liczby krawędzi między wykresami gwiazdowymi, tak że wykres jest płaski

9

Mam wykres Gktó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ćH1,H2,,Hn być różnymi wykresami gwiazd o różnych rozmiarach, które są obecne w G. Nazywamy zbiór wszystkich węzłów, które są centrami na dowolnym wykresie gwiazdowymR.

Załóżmy teraz, że te wykresy gwiezdne budują krawędzie innych wykresów gwiezdnych, tak że żadna krawędź nie występuje między żadnymi węzłami R. Następnie, ile krawędzi istnieje maksymalnie między węzłami wR i węzły, które nie są w R, czy wykres powinien pozostać płaski?

Chcę górnej granicy liczby takich krawędzi. Jedną górną granicą, o której myślę, jest: rozważ je jako dwustronny wykres płaski gdzieR jest jednym zestawem wierzchołków, a reszta wierzchołków tworzy inny zestaw A. Jesteśmy zainteresowani krawędziami między tymi zestawami (R i A). Ponieważ jest to planeta dwustronna, liczba takich krawędzi jest ograniczona dwukrotnością liczby węzłówG.

Wydaje mi się, że jest to lepsza granica, może dwa razy więcej węzłów A plus liczba węzłów w R.

Gdybyś mógł obalić moją intuicję, byłoby to również dobre. Mam nadzieję, że niektórzy z was wymyślą dobrą więź wraz z kilkoma istotnymi argumentami.

singhsumit
źródło
1
Pozwól, że powtórzę problem w inny sposób: biorąc pod uwagę płaski wykres dwuczęściowy, powiedz H, że chcemy go rozłożyć na podzbiory, gdzie każdy podzbiór odpowiada grafowi gwiazdowemu w G (rozkład węzłowy-rozłączny na powiedz „x” różnych gwiazd (zakładając, że istnieje)). więc jakie jest najściślejsze ograniczenie liczby krawędzi na płaskim dwuczęściowym wykresie H (czy „x” może w nim odgrywać dowolną rolę?).
singhsumit
6
cstheory.stackexchange.com/questions/5412/… może mieć znaczenie.
David Eppstein,
prawie wydaje się duplikatem powyższego pytania, ale nie jestem pewien.
Suresh Venkat,
Przekształcenie nie do końca wyjaśnia: jeśli masz dwustronny wykres, możesz podzielić krawędzie na gwiazdy, powielając węzły lub węzły, tracąc krawędzie. Na przykład kwadrat daje 2 gwiazdy 3-węzłowe lub 3-węzłowe i 1-węzłowe. W obu przypadkach wydaje się, że analiza i przykład @ Davida ( cstheory.stackexchange.com/questions/5412 ) odpowiada na twoje pytanie.
Jack

Odpowiedzi:

2

Twoje oświadczenie jest trochę niejednoznaczne: najpierw napisz: „… tak, aby nie było żadnej krawędzi między węzłami w R”, ale następny akapit oznacza, że ​​między wierzchołkami nie ma również krawędzi A. Zakładam również, że gwiazdy są rozłączne i że policzysz wszystkie krawędzie (w tym te początkowo obecne w gwiazdach). Załóżmy również, że są co najmniej dwie gwiazdki i przynajmniej jedna z nich ma stopień naukowy2.

W takim przypadku nie możesz pokonać 2N4 uwiązany (N= liczba wszystkich wierzchołków). Rozważ nieco inny scenariusz: zacznij od dowolnego zestawuNwierzchołki, niektóre czerwone, niektóre czarne, co najmniej dwa z każdego rodzaju. Na każdym kroku dodaj dowolnie krawędź między czerwonym i czarnym wierzchołkiem, o ile nie tworzy przecięć ani nie powiela się krawędzi. Twierdzę, że kiedy utkniesz, wszystkie cykle mają długość4.

Twój scenariusz jest szczególnym przypadkiem tego procesu, w którym najpierw tworzysz gwiazdy, a następnie dodajesz pozostałe krawędzie. Jeśli wszystkie cykle mają długość4, 2N4związany następuje. Mówiąc bardziej ogólnie, pokazuje, że bez względu na to, od którego dwustronnego wykresu zaczniesz, zawsze możesz uzupełnić go do wykresu czworokątnego (słowo, które stworzyłem).

Pokażmy teraz roszczenie. W tym procesie wszystkie ścieżki będą miały naprzemiennie czarne i czerwone wierzchołki, a każdy cykl będzie miał co najmniej długość4. Jeśli wykres nie jest połączony, możesz połączyć dowolny czerwony wierzchołek na zewnętrznej powierzchni jednego komponentu z czarnym wierzchołkiem na drugiej powierzchni innego komponentu. Możemy więc założyć, że wykres jest już podłączony.

Załóżmy, że masz twarz F długości 6 albo więcej. Fmusi mieć co najmniej trzy czarne wierzchołki (niektóre ewentualnie równe). Jeśli jakiś wierzchołekx powtarza się w dniu F, weź dwa kolejne występy zgodnie z ruchem wskazówek zegara z x, mówić xa...xb.... F musi zawierać czarny wierzchołek zx, więc w zależności od lokalizacji z, moglibyśmy się połączyć a lub b do z wewnątrz Fbez powielania krawędzi. Jeśli żaden wierzchołek się nie powtórzy, wybierz sekcję zgodną z ruchem wskazówek zegaraxaybz z F, gdzie x,y,z są czarne i a,bsą czerwone. Gdybyx jest połączony z b następnie a nie można połączyć się z z (przez płaskość), dzięki czemu możemy dodać jedną z krawędzi (x,b), (a,z) wewnątrz F.

Marek Chrobak
źródło
dzięki za odpowiedź. niektóre osoby powyżej opublikowały odpowiedni link do podobnego problemu i teraz mam odpowiedź.
singhsumit