przecięcia grafu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
magda265
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 23 sty 2013, o 15:41
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

przecięcia grafu

Post autor: magda265 »

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}\).
ODPOWIEDZ