Основні поняття графа

1. Теоретичні основи

1. Основні поняття графа

Означення

        Нехай V – непорожня множина,  – множина всіх його двохелементних підмножин. Пара , де Е – довільна підмножина множини , називається графом (неорієнтованим графом). Елементи множини V називаються вершинами графа, а елементи множини Е – ребрами.[pic 1][pic 2][pic 3]

Плоскі графи

      У багатьох випадках не має значення, як зобразити граф, оскільки ізоморфні графи несуть одну і ту ж інформацію. Однак зустрічаються ситуації, коли важливо з'ясувати, чи можливо намалювати граф на площині так, щоб його зображення задовольняло певним вимогам. Наприклад, в радіоелектроніці при виготовленні мікросхем друкованим способом електричні ланцюги наносяться на плоску поверхню ізоляційного матеріалу.  А так як провідники не ізольовані, то вони не повинні перетинатися. Аналогічне завдання виникає при проектуванні залізничних та інших шляхів, де небажані переїзди. Таким чином виникає поняття плоского графа.  

Означення

[pic 4]Плоским графом назвемо граф, вершини якого є точками площини, а ребра безперервними плоскими лініями без самоперетинів, що з'єднують відповідні вершини так, що ніякі два ребра не мають спільних точок, крім інцидентної їм обом вершини.  Приклади плоских графів дані на рисунку 1.

Означення

Будь-який граф, ізоморфний плоскому графу, називається планарним.

[pic 5]Граф  зображений на рис. 2, є планарним, так як він ізоморфний графам на рис. 1, б, в. На тій же підставі граф на рис. 3, а планарний, оскільки графи, представлені на рис. 3, а, б, ізоморфні. [pic 6]