teoria grafów-grafy planarne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
aisak7
Użytkownik
Użytkownik
Posty: 73
Rejestracja: 22 lis 2007, o 20:16
Płeć: Kobieta
Podziękował: 13 razy
Pomógł: 3 razy

teoria grafów-grafy planarne

Post autor: aisak7 »

dla jakich r mogą istnieć planarne grafy regularne stopnia r?
silvaran
Użytkownik
Użytkownik
Posty: 1300
Rejestracja: 6 sty 2009, o 20:22
Płeć: Mężczyzna
Lokalizacja: Skierniewice/Warszawa
Podziękował: 60 razy
Pomógł: 123 razy

teoria grafów-grafy planarne

Post autor: silvaran »

Wnioski ze wzoru Eulera:
Jeżeli G jest planarny, to wierzchołek o najmniejszym stopniu jest stopnia co najwyżej 5.
Jak widać musi zachodzić \(\displaystyle{ r \le 5}\)
Teraz sprawdzenie dla konkretnych r jest już banalne (wystarczy narysować odpowiednie grafy, raptem 6 ich będzie - jeśli graf trywialny jest 0-regularny )
ODPOWIEDZ