Planarni grafovi su oni grafovi koji se mogu nacrtati u ravni tako da im se grane ne seku. Preciznije, zahteva se da je graf mogućno predstaviti u ravni tako da zajednička tačka dve grane može biti samo čvor koji predstavlja zajedničku krajnju tačku tih grana. Ako je planaran graf predstavljen na opisan način u ravni, on deli ravan na više konačnih zatvorenih oblasti i jednu beskonačnu oblast.
Svaka konačna oblast se naziva okce ili ćelija. Ako je graf povezan i ne sadrži artikulacione čvorove, granična linija okca predstavlja konturu grafa. Ponekad se pod okcem podrazumeva, umesto oblasti, upravo ova granična kontura.
Ojlerova teorema o planarnim grafovima kaže da za svaki planaran graf važi n+f=m+2, gde je n broj čvorova, m broj grana, a f broj oblasti grafa. Ruski naučnici Kuratovski i Potrjagin kažu da je graf planaran ako ne sadrži kao potpodelu K3,3 ili K5.
Takođe, graf je planaran ako važi 3*|V| - |E| ≥ 6, gde je |V| broj čvorova, a |E| broj grana.[1]
Reference
Wikiwand in your browser!
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.
