teoria grafów-grafy planarne
-
- 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
Jak widać musi zachodzić \(\displaystyle{ r \le 5}\)Wnioski ze wzoru Eulera:
Jeżeli G jest planarny, to wierzchołek o najmniejszym stopniu jest stopnia co najwyżej 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 )