Graf planarny

[darksaq]

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:

AU

graf2.png (2.81 KiB) Przejrzano 101 razy

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?

[jutrvy]

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ść.