Планарни графови
Планарни графови су они графови који се могу нацртати у равни тако да им се гране не секу. Прецизније, захтева се да је граф могућно представити у равни тако да заједничка тачка две гране може бити само чвор који представља заједничку крајњу тачку тих грана. Ако је планаран граф представљен на описан начин у равни, он дели раван на више коначних затворених области и једну бесконачну област.
Свака коначна област се назива окце или ћелија. Ако је граф повезан и не садржи артикулационе чворове, гранична линија окца представља контуру графа. Понекад се под окцем подразумева, уместо области, управо ова гранична контура.
Ојлерова теорема о планарним графовима каже да за сваки планаран граф важи н+ф=м+2, где је н број чворова, м број грана, а ф број области графа. Руски научници Куратовски и Потрјагин кажу да је граф планаран ако не садржи као потподелу К3,3 или К5.
Такође, граф је планаран ако важи 3*|V| - |Е| ≥ 6, где је |V| број чворова, а |Е| број грана.[1]
Референце[уреди | уреди извор]
- ^ Стевановић, Драган; Ћирић, Мирослав; Симић, Слободан; Балтић, Владимир (2. 3. 2007). „Дискретна математика” (ПДФ). Архивирано из оригинала (ПДФ) 12. 07. 2017. г. Приступљено 24. 06. 2017.
