За граф се каже да је раван ако се може нацртати у равни тако да се ниједна ивица не укршта.

Пример: Графикон приказан на сл. је планарни граф.

дужина јава стринга

Регион графикона: Размотрите раван граф Г=(В,Е). Регион је дефинисан као област равни која је ограничена ивицама и не може се даље делити. Планарни граф дели планове на један или више региона. Један од ових региона ће бити бесконачан.

Коначна регија: Ако је површина региона коначна, онда се та област назива коначна област.

Бесконачни регион: Ако је површина региона бесконачна, та област се назива бесконачна област. Планарни граф има само једну бесконачну област.

Пример: Размотрите график приказан на слици. Одредите број региона, коначних региона и бесконачног региона.

Решење: На горњем графикону је пет региона, тј₁,р₂,р₃,р₄,р₅.

На графу постоје четири коначна региона, тј. р₂,р₃,р₄,р₅.

Постоји само једно коначно подручје, тј. р₁

Својства планарних графова:

1. Ако повезани планарни граф Г има е ивица и р области, онда је р ≦ То је.
2. Ако повезани планарни граф Г има е ивица, в врхова и р области, онда је в-е+р=2.
3. Ако повезани раван граф Г има е ивица и в темена, онда је 3в-е≧6.
4. Комплетан граф К_нје раван ако и само ако је н<5.< li>
5. Потпуни бипартитни граф К_мнје раван ако и само ако је м3.

Пример: Доказати да је комплетан граф К₄је раван.

Решење: Комплетан граф К₄садржи 4 темена и 6 ивица.

Знамо да је за повезани раван граф 3в-е≧6. Отуда за К₄, имамо 3к4-6=6 које задовољава својство (3).

образац дизајна градитеља

Тако је К₄је планарни граф. Отуда Провед.

Непланарни графикон:

За граф се каже да није раван ако се не може нацртати у равни тако да се ниједна ивица не укршта.

Пример: Графикони приказани на сл. су непланарни графови.

Ови графови се не могу нацртати у равни тако да се не укрштају ивице, па су непланарни графови.

Својства непланарних графова:

Граф је непланаран ако и само ако садржи подграф који је хомеоморфан К₅или К_3.3

хритхик росхан аге

Пример 1: Покажите да је К₅је непланарна.

Решење: Комплетан граф К₅садржи 5 врхова и 10 ивица.

Сада, за повезани планарни граф 3в-е≧6.

Дакле, за К₅, имамо 3 к 5-10=5 (што не задовољава својство 3 јер мора бити веће или једнако 6).

Дакле, К₅је непланарни граф.

Пример 2: Покажите да су графови приказани на сл. непланарни тако што ћете пронаћи подграф који је хомеоморфан К₅или К_3.3.

Решење: Ако уклонимо ивице (В₁,ИН₄),(ИН₃,ИН₄) и (В₅,ИН₄) график Г₁,постаје хомеоморфна К₅.Онда је непланарна.

Ако уклонимо ивицу В_2,В7) график Г₂постаје хомеоморфна К_3.3.Онда је непланарна.

Бојење графикона:

Претпоставимо да је Г= (В,Е) граф без више ивица. Бојење темена Г је додељивање боја врховима Г тако да суседни врхови имају различите боје. Граф Г је М-бојан ако постоји боја за Г која користи М-Боје.

Правилно бојење: Бојење је исправно ако било која два суседна темена у и в имају различите боје, иначе се назива неправилним бојењем.

Пример: Размотрите следећи графикон и боју Ц={р, в, б, и}. Обојите график правилно користећи све боје или мање боја.

како проверити величину екрана монитора

Графикон приказан на сл. има најмање 3 боје, дакле к(Г)=3

Решење: Слика приказује график правилно обојен са све четири боје.

Слика приказује график правилно обојен са три боје.

Хроматски број Г: Минимални број боја потребних да се добије правилно обојење графа Г назива се хроматски број Г и означава се са к(Г).

Пример: Хроматски број К_нје н.

Решење: Боја К_нможе се конструисати коришћењем н боја додељивањем различитих боја сваком темену. Ниједна два темена не могу бити додељена истим бојама, пошто су свака два темена овог графа суседна. Отуда и хроматски број К_н=н.

Примене бојења графова

Неке примене бојења графикона укључују:

• Додела регистра
• Мап Цолоринг
• Бипартитна провера графа
• Додела фреквенције за мобилне радио
• Израда распореда итд.

Навести и доказати теорему руковања.

Теорема руковања: Збир степени свих врхова у графу Г једнак је двоструком броју ивица у графу.

Математички се може навести као:

∑_в∈Вдег(в)=2е

Доказ: Нека је Г = (В, Е) граф где је В = {в₁,ин₂, . . . . . . . . . .} је скуп темена и Е = {е₁,То је₂. . . . . . . . . .} је скуп ивица. Знамо да свака ивица лежи између два темена тако да сваком врху даје степен један. Стога свака ивица доприноси степену два за граф. Дакле, збир степени свих врхова је једнак двоструком броју ивица у Г.

Дакле, ∑_в∈Вдег(в)=2е

јава матх пов