przecięcia grafu
-
- Użytkownik
- Posty: 22
- Rejestracja: 23 sty 2013, o 15:41
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
przecięcia grafu
Niech G będzie grafem planarnym, o zbiorze wierzchołków \(\displaystyle{ \{v_1,...,v_n\}}\) i niech \(\displaystyle{ p_1,...p_n}\) będą dowolnymi różnymi punktami płaszczyzny. Podaj heurystyczne uzasadnienie tego, że graf G może być narysowany na płaszczyźnie w taki sposób, by wierzchołki \(\displaystyle{ v_i}\) znalazły się w punktach \(\displaystyle{ p_i}\) dla każdego \(\displaystyle{ i}\).