Ravninski graf

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Zgledi grafov
ravninski neravninski
CGK4PLN.svg
polni graf
K4
(tetraedrski graf)
Complete graph K5.svg
polni graf K5
Butterfly graph.svg
metulj
Biclique K 3 3.svg
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]

  1. 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[uredi | uredi kodo]

  1. Trudeau (1993), str. 64.

Viri[uredi | uredi kodo]