Задання графів

Щоб задати будь-який граф, треба задати множини його вершин і ребер.

Надалі будемо розглядати скінченні графи. Нехай граф має n вершин і k ребер. Задати скінченні графи можна різними способами: списком ребер, фактор-множиною, матрицею інцидентності, матрицею суміжності.

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

Приклад. Нехай дано граф:

У цього графа вершина b ізольована. Задамо його різними способами.

Задамо граф списком ребер і додамо до цього списку ізольовану вершину: .

П ри заданні графа у вигляді фактор-множини записуються пари , де — переріз відношення U за елементом з врахуванням кратності ребер.

Приклад. Задамо граф у вигляді фактор-множини:

.

Можна побудувати матрицю інцидентності (ще кажуть: інциденцій) графа. Матрицею інцидентності є прямокутна матриця з n рядками, які позначаються елементами множини вершин V, і m стовпчиками які позначаються елементами множини ребер U. Така матриця в кожному стовпчику має по два ненульові елементи. Для простого графа вона не має двох однакових стовпчиків. Якщо задається мультиграф, то в ньому з’являються однакові стовпчики, які відповідають кратним ребрам. При цьому , якщо вершина не інцидентна ребру ; , якщо вершина є кінцем дуги або неорієнтованого ребра ; , якщо вершина є початком дуги . Така матриця однозначно задає граф. Матрицю інциденцій будують для графів, які не мають петель. Якщо граф має петлі, то матрицю треба розбити на дві підматриці: додатну й від’ємну. Часом, коли є петлі, то у відповідних позиціях ставлять 2.

Хоч матриця інцидентності задає граф однозначно, проте вона не ефективна, оскільки містить багато нулів

Приклад. Задамо за допомогою матриці інцидентності:

Матрицею суміжності (ще кажуть: матрицею сусідства) є квадратна матриця , рядки і стовпчики якої позначаються елементами множини вершин V. Елемент дорівнює кількості ребер, які йдуть із вершини у вершину . При цьому, якщо граф орієнтований, то в загальному випадку , тобто матриця не симетрична; якщо граф неорієнтований, то . Матриця суміжності визначає граф з точністю до заміни будь-якого неорієнтованого ребра парою протилежно направлених дуг між цими ж вершинами; але задання орієнтованих графів матрицею суміжності однозначне. Якщо граф не є мультиграфом (тобто не має кратних ребер), то його матриця суміжності є характеристичною матрицею відношення U.

Приклад. Задамо граф матрицею суміжності:

Плоскі й неплоскі графи

Графічно будь-який скінченний (і навіть злічуваний) граф можна подати у тривимірному просторі, причому, якщо граф не містить кратних ребер, то його ребра можна зобразити прямолінійними відрізками. На площині реалізується не будь-який граф. Через це графи поділяються на плоскі (ще кажуть: планарні) й неплоскі (ще кажуть: непланарні). Проте навіть неплоский граф можна подати на площині: при цьому деякі його ребра будуть перетинатися, але в точках їхнього перетину вершин не буде.

Г раф є плоским, якщо його можна намалювати без перетину ребер (зображений третім граф є повним плоским графом з найбільшою кількістю вершин):

Наведені нижче графи є неплоскими, їх називають графами Понтрягіна-Куратовського і відповідно позначають і :

Два графи називаються гомеоморфними, якщо після вилучення з них вершин другого степеня і об’єднання інцидентних цим вершинам ребер вони стають ізоморфними.

Приклад. У наведених нижче графів вершини е і f мають другий степінь.

Після вилучення цих вершин два перші графи стануть ізоморфними третьому графові. Отже, всі три графи гомеоморфні.

Легко можна показати, що граф, гомеоморфний плоскому графові, також є плоским, а граф, гомеоморфний неплоскому графові, є неплоским.

Підграфом графа називається граф, у який входить лише частина вершин графа G, які утворюють множину А, разом з усіма ребрами (дугами) , що їх з’єднують. Таким чином , , .

Теорема. Граф є плоским тоді і тільки тоді, коли жоден його підграф не гомеоморфний жодному з графів Понтрягіна-Куратовського.

?????Теорема Ейлера. У будь-якому простому плоскому графі є вершина, степінь якої не більший від 5.