Jak ustalić, czy wykres planarny może zostać wygenerowany przez sekwencję stopni?
Dla następujących sekwencji stopni wykresów,
$2,2,2,3,3,3,3,4,5,5\\1,1,1,1,2,2,2,2,3,3$
który może być sekwencją stopni prostego nie skierowanego wykresu, który jest połączony i płaski?
Myślę, że tylko druga może być prawidłową sekwencją. Czy istnieje ogólna zasada oceniania, czy sekwencja stopni może generować wykres planarny?
Odpowiedzi
Ogólnie będzie to wymagało zastanowienia się, czy sekwencja stopni jest taka jak na wykresie planarnym. Na przykład, spójrz na to pytanie, aby zapoznać się z możliwymi strategiami, które obejmują użycie twierdzenia Kuratowskiego lub dobrze znanego ograniczenia krawędzi$3n - 6$. Możesz również obliczyć średni stopień, który dla wykresu planarnego musi być ściśle mniejszy niż 6. (Zobacz Kryterium płaskości ). Zauważysz, że często sprawdzamy, czy wykres narusza którekolwiek z kryteriów.
Obie sekwencje mogą przedstawiać planarny wykres.
Dla $2,2,2,3,3,3,3,4,5,5$możesz zauważyć kilka rzeczy. Ponieważ zakładamy$G$ jest połączone, $G$ nie może być drzewem (nie ma stopni $1$wierzchołki), a zatem ma cykl. Jednak,$|E(G)| = 16 \le 3(10) - 6 = 24$, więc nie ma szczęścia (pamiętaj, że możemy użyć tego powiązania tylko do udowodnienia, że wykres jest niepłaski ). Być może po zabawie możesz pomyśleć, że istnieje wykres planarny i miałbyś rację. Używając algorytmu Havela-Hakimi , zatrzymując się na krótko, gdy otrzymałem sekwencję stopni ścieżki$8$ wierzchołki, znajdujemy następujący wykres:

Z tego przykładu widzimy, że niekoniecznie tak jest $G$ ma cykl, ale nie ma trójkąta (co umożliwiłoby nam użycie ulepszonej granicy $2n-4$). Nawet wtedy,$|E(G)| = 16 = 2(10) - 4$.
Dla $1,1,1,1,2,2,2,2,3,3$, możesz szybko zauważyć, że ten wykres nie może zawierać $K_5$ lub $K_{3,3}$jako podpodział i dlatego musi być płaski. Wykorzystuje to twierdzenie Kuratowskiego. Nie powinno też być trudno znaleźć drzewo z taką sekwencją stopni.
W pierwszej sekwencji możesz to od razu zauważyć $G$ nie może mieć $K_5$ jednak podział $K_{3,3}$może wymagać więcej rozumowania. To znaczy, w przeciwieństwie do drugiej sekwencji, pokazaliśmy, że pierwsza sekwencja może reprezentować wykres planarny, ale nie pokazaliśmy, że musi .