Zadanie: czy istnieje graf nieskierowany o następujących stopniach wierzchołków:
1, 1, 3, 3, 3, 4, 6, 7?
Próbuję narysować taki graf:
- wierzchołek o stopniu 7 łączę ze wszystkimi pozostałymi, mam więc jeden o stopniu 7 i siedem o stopniu 1
- wybieram jeden z wierzchołków o stopniu jeden i łączę z pięcioma innymi o stopniu 1: mam teraz jeden o stopniu 7, jeden o stopniu 6, pięć o stopniu 2 i tylko jeden o stopniu 1 (czyli już na tym etapie brakuje mi drugiego wierzchołka o stopniu 1)
Wnioskuję, że taki graf nie istnieje.
Pytanie jest takie: czy istnieje jakiś formalny warunek na stopnie wierzchołków, który w tym przypadku nie jest spełniony?
stopnie wierzchołków grafu
-
- Użytkownik
- Posty: 5
- Rejestracja: 10 sie 2013, o 12:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
stopnie wierzchołków grafu
Podbijam. Domyślam się że warunek, że suma stopni ma być parzysta to za mało?
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
stopnie wierzchołków grafu
Huub900, W pierwszym poście prawie udowodniłeś, że taki graf nie istnieje. Można to ubrać w trochę bardziej matematyczne narzędzia (zasada szufladkowa Dirichleta).
-
- Użytkownik
- Posty: 5
- Rejestracja: 10 sie 2013, o 12:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
stopnie wierzchołków grafu
Kod: Zaznacz cały
http://www.dcs.gla.ac.uk/~pat/af2009/mySlides/Havel-Hakimi.ppt