Mam wykres któ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ć być różnymi wykresami gwiazd o różnych rozmiarach, które są obecne w . Nazywamy zbiór wszystkich węzłów, które są centrami na dowolnym wykresie gwiazdowym.
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 . Następnie, ile krawędzi istnieje maksymalnie między węzłami w i węzły, które nie są w , 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 gdzie jest jednym zestawem wierzchołków, a reszta wierzchołków tworzy inny zestaw . Jesteśmy zainteresowani krawędziami między tymi zestawami ( i ). Ponieważ jest to planeta dwustronna, liczba takich krawędzi jest ograniczona dwukrotnością liczby węzłów.
Wydaje mi się, że jest to lepsza granica, może dwa razy więcej węzłów plus liczba węzłów w .
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.
źródło
Odpowiedzi:
Twoje oświadczenie jest trochę niejednoznaczne: najpierw napisz: „… tak, aby nie było żadnej krawędzi między węzłami wR ”, 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ń naukowy≥2 .
W takim przypadku nie możesz pokonać2N−4 uwiązany (N = liczba wszystkich wierzchołków). Rozważ nieco inny scenariusz: zacznij od dowolnego zestawuN wierzchoł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 , 2N−4 zwią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 twarzF długości 6 albo więcej. F musi 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ć x−a−...−x−b... . F musi zawierać czarny wierzchołek z≠x , więc w zależności od lokalizacji z , moglibyśmy się połączyć a lub b do z wewnątrz F bez powielania krawędzi. Jeśli żaden wierzchołek się nie powtórzy, wybierz sekcję zgodną z ruchem wskazówek zegarax−a−y−b−z z F , gdzie x,y,z są czarne i a,b są 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 .
źródło