From Wikipedia, the free encyclopedia
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.[lower-alpha 1] 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.
Zgledi grafov | |
---|---|
ravninski | neravninski |
polni graf K4 (tetraedrski graf) |
polni graf K5 |
metulj |
graf napeljav K3,3 |
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.