czy istnieje graf o stopniach wierzchołków

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
anilahcim
Użytkownik
Użytkownik
Posty: 209
Rejestracja: 13 lip 2012, o 14:32
Płeć: Kobieta
Lokalizacja: Pcim
Podziękował: 107 razy

czy istnieje graf o stopniach wierzchołków

Post autor: anilahcim »

Jak pokazać, że nie istnieje graf o ciągu stopni wierzchołków \(\displaystyle{ (7,7,7,3,3,3,2,2)}\)?
Andreas
Użytkownik
Użytkownik
Posty: 1130
Rejestracja: 1 lis 2008, o 22:33
Płeć: Mężczyzna
Podziękował: 72 razy
Pomógł: 156 razy

czy istnieje graf o stopniach wierzchołków

Post autor: Andreas »

Skorzystaj z algorytmu Havla-Hakimiego.

W treści zadania oczywiście chodziło o graf prosty.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

czy istnieje graf o stopniach wierzchołków

Post autor: »

Prościej na palcach - skoro wierzchołków jest osiem, a trzy z nich mają mieć stopień \(\displaystyle{ 7}\), to znaczy, że są połączone ze wszystkimi pozostałymi. Stąd wniosek, że wszystkie pozostałe musiałyby mieć stopień co najmniej \(\displaystyle{ 3}\).

Q.
ODPOWIEDZ