stopnie wierzchołków grafu

Huub900 · Post autor: **Huub900** » 14 cze 2012, o 17:58

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?

pavel3643 · Post autor: **pavel3643** » 24 sie 2013, o 15:28

Podbijam. Domyślam się że warunek, że suma stopni ma być parzysta to za mało?

Huub900 · Post autor: **Huub900** » 25 sie 2013, o 23:05

Zdecydowanie za mało, bo w tym przypadku jest spełniony.

bakala12 · Post autor: **bakala12** » 26 sie 2013, o 10:04

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).

pavel3643 · Post autor: **pavel3643** » 5 paź 2013, o 13:12

Kod: Zaznacz cały

http://www.dcs.gla.ac.uk/~pat/af2009/mySlides/Havel-Hakimi.ppt