Síkba-rajzolható gráf Egy G=(V, E) gráf síkba-rajzolható, ha létezik egy olyan lerajzolása síkban, ahol az élek nem metszik egymást.
Tétel: Egy gráf pontosan akkor síkba-rajzolható, ha gömbre rajzolható.
Biz.: Sztereografikus projekció. A gömböt a síkra helyezzük (déli pólusával), majd az északi pólusából egyeneseket húzunk a gráf síkba/gömbre rajzolásának összes pontjához. Ezen egyeneseknek a gömbbel/síkkal vett metszéspontja lesz a vetített képpont. A le/felvetített kép nem méterarányos, de a metszéseket biztosan megtartja. (A gömb elhelyezésénél figyelnünk kell arra, hogy az északi póluson ne legyen pontja a gömbrerajzolásának – ez mindig kivitelezhető.)
A síkbarajzolt gráf a síkot tartományokra bontja.
Állítás: Egy síkbarajzolható gráf bármely tartománya lehet (egy másik) síkbarajzolásnál külső tartomány.
Biz.: Tegyük fel, hogy a G gráf síkba van rajzolva, ti egy belső tartománya. Helyezzünk el egy gömböt úgy, hogy ti belső pontjában érintse a síkot. Vetítsük fel a gráfot sztereografikus projekcióval. Ekkor a déli pólus esik a ti gömbi képébe. Forgassuk el a gömböt úgy, hogy az északi és a déli pólus cserélődjön fel. Ekkor a sztereografikus síkra vetítésnél ti lesz a külső tartomány.
Szerzők: yoda
[Szócikk szerkesztése]
[Lexikon kezdőlapra lépés]
|
