Irányított gráfok lerajzolása
Egy irányított 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.
-
Egy uv élnek önmagát nem metsző görbét feleltetünk meg,
amely görbe két végpontja az u-t reprezentáló,
illetve v-t reprezentáló pont. Azaz az uv él göbéje az u-t és v-t
reprezentáló ``karikákat'' köti össze. v karikájánál a
görbére egy nyílhegyet rajzolunk, így a görbe
egy nyíl lesz, amley iránya tükrözi az irányítást.
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.