Page 10 - 4336

Риисунок 11.3 – Прииклади пповних гграфів

Каажуть, щщо графф “уклаадаєтьсяя на пллощині”,, якщо він

ізоморффний (однаковиий за фформою) графу, вершинни якогго є
точкамии площиини, а реебра – ннеперервними лініями пллощини без

самоперретинів, що з'єдннують ввідповіднні вершиини, приичому жоодні
два ребрра не маають спілльних тоочок, кріім вершиини, інццидентноої їм

обом.
Плланарнимм називвається граф, який мможна уукласти на

площинні, плоскким – грраф, якиий уже уукладеноо на плоощині (ррис.
1.4). Тааким чиином плланарниим називвається граф, іізоморффний

деякомуу плоскоому граффу. Меррежі дорріг є здеббільшогоо плоскиими
графамии, за вииняткомм локалььних сиитуацій, таких як склаадні

дорожнні розв'яззки.

а б

Риссунок 1.44 – Планнарний (аа) та відпповіднийй йому пплоский

графф (б). Пуунктиромм показанно переннесені веершини та ребраа

1.2 Степінь ввершинии графаа

Сттепенемм вершинни v в гррафі G нназиваєтьься кільккість ребер,

інциденнтних веершині v і познначаєтьсся δ(v). Множинну вершшин,

суміжниих з ввершиною v, ппозначаюють O(vv). Очеевидно, що

|O(v)|=δδ(v).

10