Narysuj graf G planarny \(\displaystyle{ |V|=6}\), sprawdź warunek \(\displaystyle{ m\le3n-6}\). Ile można dorysować krawędzi, aby graf pozostał planarny?
Nie wiem o co dokładnie chodzi z tym warunkiem, co mam nim sprawdzić.
Rysunek zrobiłem tak:
1) Graf planarny o 6 wierzchołkach
2) Graf planarny z większą ilością krawędzi
Chciałbym prosić o sprawdzenie czy one są też dobrze rozrysowane?
Graf planarny
- jutrvy
- Użytkownik
- Posty: 1202
- Rejestracja: 24 lis 2014, o 18:04
- Płeć: Mężczyzna
- Podziękował: 10 razy
- Pomógł: 239 razy
Re: Graf planarny
Ten drugi graf nie jest grafem planarnym o sześciu wierzchołkach z maksymalną liczbą krawędzi. Można jeszcze dorysować do niego krawędzie tak, żeby został planarny. Twoim zadaniem jest dorysowanie ich tylu, żeby dorysowanie jakiejkolwiek innej zepsuło planarność.