Gráfok lerajzolása
Egy gráf (síkon történő) lerajzolása alatt a következőt
értjük:
-
A csúcsoknak a sík pontjait feleltetjük meg. Különböző
csúcsoknak különböző pontok felelnek meg. a csúcsokat
reprezentáló pontokat karikákkal jelöljük.
-
A nem-hurokéleknek önmagukat nem metsző nyilt görbéket feleltetünk meg.
Az x-et és y-t összekötő élnek megfelelő görbe
két végpontja az x-et reprezentáló,
illetve y-t reprezentáló pont. Azaz az xy él göbéje az x-t és y-t
reprezentáló ``karikákat'' köti össze.
-
Hurokéleknek önmagukat nem metsző zárt görbéket feleltetünk meg.
Az x-re illeszkedő élnek megfelelő zárt görbe
egybeeső két végpontja az x-et reprezentáló pont.
Azaz az xx él görbéje az x-et reprezentáló karikán áthaladó
Jordan-görbe.
Hogy az így kapott ábáról az éleket vissza tudjuk fejteni további
feltételekkel kell élnünk.
-
Egy e élt reprezentáló görbe
végpontjain kívül
további csúcsot reprezentáló pontot (karikát)
nem érint.
-
Két élt reprezentáló görbe ``szépen találkozik''.
Azaz véges sok közös pontjuk van és ha egy közös
belső pontban a két görbe átmetszi egymást.
Azaz két élt reprezentáló görbe esetén közös
pontjuk egy közös végpont (ez akkor és csak akkor
fordul elő, ha a két élnek van közös végpontja)
vagy egy közös belső pont, amikor is a két görbe
átmetszi egymást.
A karikák szerepe onnan ered, hogy rajzunkon világos legyen, hogy
több görbe összefutásának pontjáról tudhassuk, hogy egy csúcsot
reprezentáló pont, vagy két (esetleg gráfelméletileg diszjunkt)
él metszéspontja.
Ha görbék helyett csak nagyon speciális görbéket, tört vonalakat
engedünk meg, akkor lényegében ugyanehhez a fogalomhoz jutunk.