S7: Rovinné grafy
1. Ktoré z nasledujúcich grafov sú rovinné grafy?
2. Ukážte, že grafy K5 a K3,3 nie sú rovinné. Nakreslite diagramy týchto grafov tak, aby sa čo najmenší počet ich hrán pretínal.
3. Dokážte, že strom je rovinný graf.
4. Je Petersenov graf rovinný?
5. Dokážte, že ak je rovinný graf s vrcholmi, tak pre počet hrán platí: . Nakreslite diagram grafu, pre ktorý platí rovnosť.
6. Dokážte, že ak pre všetky stupne vrcholov vi platí deg(vi) = 3 , tak počet všetkých uholníkových oblastí je rovný číslu .
- 19 apríla 2016, 23:44