Планарни графикон:
За граф се каже да је раван ако се може нацртати у равни тако да се ниједна ивица не укршта.
Пример: Графикон приказан на сл. је планарни граф.
Регион графикона: Размотрите раван граф Г=(В,Е). Регион је дефинисан као област равни која је ограничена ивицама и не може се даље делити. Планарни граф дели планове на један или више региона. Један од ових региона ће бити бесконачан.
Коначна регија: Ако је површина региона коначна, онда се та област назива коначна област.
Бесконачни регион: Ако је површина региона бесконачна, та област се назива бесконачна област. Планарни граф има само једну бесконачну област.
Пример: Размотрите график приказан на слици. Одредите број региона, коначних региона и бесконачног региона.
Решење: На горњем графикону је пет региона, тј 1 ,р 2 ,р 3 ,р 4 ,р 5 .
На графу постоје четири коначна региона, тј. р 2 ,р 3 ,р 4 ,р 5 .
Постоји само једно коначно подручје, тј. р 1
Својства планарних графова:
- Ако повезани планарни граф Г има е ивица и р области, онда је р ≦
То је. - Ако повезани планарни граф Г има е ивица, в врхова и р области, онда је в-е+р=2.
- Ако повезани раван граф Г има е ивица и в темена, онда је 3в-е≧6.
- Комплетан граф К н је раван ако и само ако је н <5. < li>
- Потпуни бипартитни граф К мн је раван ако и само ако је м3.
Пример: Доказати да је комплетан граф К 4 је раван.
Решење: Комплетан граф К 4 садржи 4 темена и 6 ивица.
Знамо да је за повезани раван граф 3в-е≧6. Отуда за К 4 , имамо 3к4-6=6 које задовољава својство (3).
Тако је К 4 је планарни граф. Отуда Провед.
Непланарни графикон:
За граф се каже да није раван ако се не може нацртати у равни тако да се ниједна ивица не укршта.
Пример: Графикони приказани на сл. су непланарни графови.
Ови графови се не могу нацртати у равни тако да се не укрштају ивице, па су непланарни графови.
Својства непланарних графова:
Граф је непланаран ако и само ако садржи подграф који је хомеоморфан К 5 или К 3.3
Пример 1: Покажите да је К 5 је непланарна.
Решење: Комплетан граф К 5 садржи 5 врхова и 10 ивица.
Сада, за повезани планарни граф 3в-е≧6.
Дакле, за К 5 , имамо 3 к 5-10=5 (што не задовољава својство 3 јер мора бити веће или једнако 6).
Дакле, К 5 је непланарни граф.
Пример 2: Покажите да су графови приказани на сл. непланарни тако што ћете пронаћи подграф који је хомеоморфан К 5 или К 3.3 .
Решење: Ако уклонимо ивице (В 1 ,ИН 4 ),(ИН 3 ,ИН 4 ) и (В 5 ,ИН 4 ) график Г 1 ,постаје хомеоморфна К 5 .Онда је непланарна.
Ако уклонимо ивицу В 2,В 7) график Г 2 постаје хомеоморфна К 3.3 .Онда је непланарна.
Бојење графикона:
Претпоставимо да је Г= (В,Е) граф без више ивица. Бојење темена Г је додељивање боја врховима Г тако да суседни врхови имају различите боје. Граф Г је М-бојан ако постоји боја за Г која користи М-Боје.
Правилно бојење: Бојење је исправно ако било која два суседна темена у и в имају различите боје, иначе се назива неправилним бојењем.
Пример: Размотрите следећи графикон и боју Ц={р, в, б, и}. Обојите график правилно користећи све боје или мање боја.
Графикон приказан на сл. има најмање 3 боје, дакле к(Г)=3
Решење: Слика приказује график правилно обојен са све четири боје.
Слика приказује график правилно обојен са три боје.
Хроматски број Г: Минимални број боја потребних да се добије правилно обојење графа Г назива се хроматски број Г и означава се са к(Г).
Пример: Хроматски број К н је н.
Решење: Боја К н може се конструисати коришћењем н боја додељивањем различитих боја сваком темену. Ниједна два темена не могу бити додељена истим бојама, пошто су свака два темена овог графа суседна. Отуда и хроматски број К н =н.
Примене бојења графова
Неке примене бојења графикона укључују:
- Додела регистра
- Мап Цолоринг
- Бипартитна провера графа
- Додела фреквенције за мобилне радио
- Израда распореда итд.
Навести и доказати теорему руковања.
Теорема руковања: Збир степени свих врхова у графу Г једнак је двоструком броју ивица у графу.
Математички се може навести као:
∑ в∈В дег(в)=2е
Доказ: Нека је Г = (В, Е) граф где је В = {в 1 ,ин 2 , . . . . . . . . . .} је скуп темена и Е = {е 1 ,То је 2 . . . . . . . . . .} је скуп ивица. Знамо да свака ивица лежи између два темена тако да сваком врху даје степен један. Стога свака ивица доприноси степену два за граф. Дакле, збир степени свих врхова је једнак двоструком броју ивица у Г.
Дакле, ∑ в∈В дег(в)=2е
