Ravninski graf
| Zgledi grafov | |
|---|---|
| ravninski | neravninski |
 polni graf K4 (tetraedrski graf) |
 polni graf K5 |
 metulj |
 graf napeljav K3,3 |
Ravninski graf je v teoriji grafov graf, ki se ga lahko vloži v ravnino – lahko se ga nariše v ravnini tako, da se njegove povezave sekajo le v svojih krajiščih, oziroma v točkah grafa. Drugače rečeno – lahko se ga nariše tako, da se nobena povezava ne seka z drugo.[a] Takšna slika se imenuje ravninska vložitev grafa. Ravninska vložitev grafa se lahko definira kot ravninski graf s preslikavo iz vsake točke grafa v točko ravnine in iz vsake povezave v ravninsko krivuljo na tej ravnini, tako da so krajne točke vsake krivulje točke, preslikane iz njenih končnih točk, in vse krivulje so disjunktne, razen v svojih krajiščih.
Vsak graf, ki se lahko nariše v ravnini, se lahko nariše tudi na sferi in obratno.
Ravninski grafi se lahko zakodirajo s kombinatoričnimi preslikavami.
Ekvivalenčni razred topološko ekvivalentnih slik na sferi se imenuje ravninska preslikava. Čeprav ima ravninski graf zunanjo ali neomejeno ploskev, nobena od ploskev ravninske preslikave nima posebnega statusa.
Posplošitev ravninskih grafov so grafi, ki se lahko narišejo na ploskev z danim rodom. V tem izrazju imajo ravninski grafi rod enak 0, ker sta ravnina (in sfera) ploskvi z rodom 0.
Opombe[uredi | uredi kodo]
Sklici[uredi | uredi kodo]
- ↑ Trudeau (1993), str. 64.
Viri[uredi | uredi kodo]
- Trudeau, Richard J. (1993), Introduction to Graph Theory (popr., pov. izd.), New York: Dover Pub., COBISS 39047469, ISBN 978-0-486-67870-2, pridobljeno 8. avgusta 2012
- Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1
