Ravninski graf

Zgledi grafov
ravninski	neravninski
polni graf K₄ (tetraedrski graf)	polni grafK₅
metulj	graf napeljav K_3,3

Ravninski grafje vteoriji grafov graf,ki se ga lahkovloživravnino– lahko se ganarišev ravnini tako, da se njegovepovezavesekajo le v svojihkrajiščih,oziroma vtočkahgrafa. Drugače rečeno – lahko se ga nariše tako, da se nobena povezava ne seka z drugo.^[a]Takšna slika se imenujeravninska vložitev grafa.Ravninska vložitev grafa se lahko definira kot ravninski graf s preslikavo iz vsake točke grafa vtočkoravnine in iz vsake povezave vravninsko krivuljona tej ravnini, tako da so krajne točke vsake krivulje točke, preslikane iz njenih končnih točk, in vse krivulje sodisjunktne,razen v svojih krajiščih.

Vsak graf, ki se lahko nariše v ravnini, se lahko nariše tudi nasferiin obratno.

Ravninski grafi se lahko zakodirajo skombinatoričnimi preslikavami.

Ekvivalenčni razred topološko ekvivalentnihslik na sferi se imenujeravninska preslikava.Čeprav ima ravninski grafzunanjoalineomejenoploskev, nobena od ploskev ravninske preslikave nima posebnega statusa.

Posplošitev ravninskih grafov so grafi, ki se lahko narišejo naploskevz danimrodom.V tem izrazju imajo ravninski grafirodenak 0, ker sta ravnina (in sfera) ploskvi z rodom 0.

Opombe

↑Tako ravninski graf, če se ga nariše na ravno ploskev, nima presečišč povezav ali pa se lahko nariše brez njih.^[1]

Sklici

↑Trudeau (1993),str. 64.

Viri

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

Ta matematični članek ješkrbina.Pomagajte Wikipediji in garazširite.

[2] Tako ravninski graf, če se ga nariše na ravno ploskev, nima presečišč povezav ali pa se lahko nariše brez njih.^[1]

[1] Trudeau (1993),str. 64.

[a]

[1]