Графи та їх застосування

 

Рис.1.16.

Приклад 1.2. Для графа, зображеного на рис.1.17. знайти матрицю інцидентності.

Рис.1.17.

Розв’язання:

Матриця інцидентності подана в таблиці 2.

Матриця інцидентності  для графа, зображеного  на рис.1.17.             Таблиця 2

	v1	v2	v3	v4	v5	v6	v7
e1	-1	1	0	0	0	0	0
e2	-1	0	1	0	0	0	0
e3	0	-1	0	1	0	0	0
e4	0	0	-1	0	1	0	0
e5	0	0	-1	0	0	1	0
e6	0	0	-1	0	0	0	1
e7	0	0	0	0	0	0	2
e8	0	-1	1	0	0	0	0

 

У кожному рядку матриці  інцидентності неорієнтованого  графа є тільки елементи, відмінні від 0 ( або 1, якщо ребро є петлею). Тому такий спосіб задання графа  – не досить економний.

Відношення інцидентності  ще можна задати за допомогою списку ребер. Кожен рядок цього списку відповідає ребру, в ньому записано номери вершин, інцидентних йому. Для  неорієнтованого графа порядок  цих вершин у рядку довільний, для орієнтованого – першими  записують номер або іншу назву  початку ребра, а другим – його закінчення [36, c.182].

За списком ребер графа  можна легко визначити матрицю  інцидентності. Справді, кожен рядок  цього списку відповідає рядку матриці  з тим самим номером.  Для  неорієнтованого графа в рядку  списку записують номери елементів  матриці інцидентності, що дорівнюють 1, а для неорієнтованого графа  в цьому рядку першим зазначають номер елемента рядка матриці, який дорівнює -1, другим – номер елемента, що дорівнює 1.

1.2.2. Задання графа  за допомогою матриці суміжності

 

Матриця суміжності графа  – це квадратна матриця ∆ = || δ_ij ||, стовпці і рядки якої відображають вершини графа. Для неорієнтованого графа δ_ij дорівнює кількості ребер, інцидентних і-й та j-й вершинам; для орієнтованого графа цей елемент матриці суміжності відповідає кількості ребер з початком в  і-й вершині та кінцем в j-й. Отже,  матриця суміжності неорієнтованого графа є симетричною (δi_ij= δ_ji), а орієнтованого графа - необов’язково. Якщо вона все-таки симетрична, то для кожного ребра орієнтованого графа існує ребро, що з’єднує ті самі вершини, але йде у зворотному напрямку. Очевидно, що орієнтований граф із симетричною матрицею суміжності канонічно відповідає неорієнтованому графу, що має ту ж саму матрицю суміжності [36, c.178].

Матриці суміжності розглянутих  вище графів, зображених на рис.1 і рис.2  наведено в таблиці нижче.

Матриця суміжності повністю визначає відповідний неорієнтований граф або орієнтований граф. Кількість  його вершин дорівнює вимірності матриці n, і-й та j-й вершинам графа інцидент ними є δij ребер. Для неорієнтованого графа δij = δji , і всі його ребра визначаються верхнім правим трикутником матриці, розміщеним над діагоналлю, включаючи останню. В обох випадках за допомогою матриці суміжності легко будується, наприклад, список ребер, що визначає граф.

 

Матриці суміжності для графів, зображених на рис.1.16, і рис.1.17     Таблиця 3

	v1	v2	v3	v4	v5	v6	v7
v1	0	1	1	0	1	0	0
v2	1	0	0	1	0	1	0
v3	1	0	0	1	1	0	0
v4	0	1	1	0	0	1	0
v5	1	0	1	0	0	1	1
v6	0	1	0	1	1	0	1
v7	0	0	0	0	1	1	0

а)

 

 

	v1	v2	v3	v4	v5	v6	v7
v1	0	1	1	0	0	0	0
v2	0	0	1	1	0	0	0
v3	0	0	0	0	1	1	1
v4	0	0	0	0	0	0	0
v5	0	0	0	0	0	0	0
v6	0	0	0	0	0	0	0
v7	0	0	0	0	0	0	1

б)

Елементу матриці суміжності, розміщеного в і-му та j-му стовпці, відповідають δij рядків списку ребер ( при δij = 0 немає жодного рядка ), в кожному з яких записують номери і та j. Для неорієнтованого графа ці рядки відповідають тільки елементам названого вище верхнього правого трикутника матриці суміжності, тобто елементам δij з j ≥ i, а для орієнтованого графа потрібно розглядати всі елементи δij [36, c.179].

1.3. Ізоморфізм графів

 

Буквальний  переклад  слова  “ізоморфізм”  означає  “однаковість  форми”.  Форма графа – це  його структура. Таким чином, ізоморфізм графів означає однаковість їх структури. Зробимо необхідні уточнення. Два графи G₁= (V₁ , E₁) і G₂ = (V₂ , E ₂)  називаються ізоморфними (це позначається      G₁ ≅ G₂), якщо між множинами їх вершин існує взаємно-однозначне відображення φ : V₁→V₂, яке зберігає суміжність, тобто для довільних вершин v і w,   (v, w)∈E₁  тоді і тільки  тоді,  коли  (φ(v), φ(w))∈ Е₂.  При цьому φ називається ізоморфним відображенням  або ізоморфізмом  графа  G₁   на  граф  G₂.  На  рис. 1.18, а, б  наведено дві пари ізоморфних графів.

Рис.1.18.

Про ізоморфні графи кажуть, що вони рівні з точністю до ізоморфізму. Ізоморфізм  графа  на  себе  називається  автоморфізмом.  Очевидно,  що  тотожне відображення  множини вершин  графа є автоморфізмом  (цей  автоморфізм називається  тривіальним).  Неважко  також  переконатися,  що  якщо  φ  є ізоморфізмом графа G₁ на граф G₂, то відображення φ^-1  є ізоморфізмом G₂  на G₁ [19, c.41-43].

Крім того, якщо є ізоморфізм φ графа G₁  на граф G₂  і ізоморфізм γ графа G₂  на G₃, то їх композиція φ°γ буде ізоморфізмом G₁ на G₃.

Теорема 1.1.  Графи ізоморфні тоді  й тільки  тоді,  коли  ізоморфні їхні доповнення.

  Доведення: Нехай G₁= (V₁, E₁), G₂ = (V₂, E₂), G₁ ≅ G₂  і φ : V₁→V₂  — ізоморфізм G₁  на G₂. Розглянемо графи G₁ = (V₁, E₁),  G₂  = (V₂, E₂). Нехай v та w — довільні вершини графа G₁.  За  означеннями доповнення  та  ізоморфізму (v, w)∈ E₁ ⇔  (v, w)∉E₁  ⇔ (φ(v), φ(w))∉E₂  ⇔  (φ(v), φ(w))∈ E₁,  тобто доповнення  ізоморфні,  причому з тим самим відображенням φ. 

Доведено

Теорема 1.2. Якщо φ — ізоморфізм графа G₁ на G₂, то вершини v у графі G₁ і φ(v) у G₂  мають однакові степені.

Доведення:  Нехай G₁ = (V₁, E₁), G₂  = (V₂, E₂) і v∈V₁. Якщо v не має суміжних вершин, то і φ(v) не може мати таких, тобто δ(v) = δ(φ(v)) = 0. Якщо v має суміжні вершини, то, за означенням ізоморфізму, для будь-якої вершини w маємо: w∈O(v) тоді й тільки тоді, коли φ(w)∈O(φ(v)). Отже,    |O(v)| = |O(φ(v))|, тобто δ(v) = δ(φ(v)). 

Доведено

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

Теорема 1.3. Ізоморфні графи мають однакову кількість вершин.

Доведення: Це  випливає  з  існування  взаємно  однозначної  відповідності  між  множинами вершин. 

Доведено

Ізоморфізм  φ  можна продовжити  на  множину ребер наступним чином: покладемо φ'((v, w)) = (φ(v), φ(w)).  З властивостей φ  випливає,  що  відображення φ' : E₁→E₂  є взаємно однозначним. Звідcи маємо наступну теорему.

Теорема 1.4. Ізоморфні графи мають однакову кількість ребер.

Теорема 1.5. Ізоморфні графи для довільного k (k ≥ 0) мають однакову кількість вершин степеня k.

Доведення: Нехай G₁ = (V₁, E₁), G₂ = (V₂, E₂), φ : V₁→V₂ — ізоморфізм графа G₁ на граф G₂, v∈V₁   і δ(v) = k.  За  теоремою 4  δ(φ(v)) = k,  тому  ізоморфізм  взаємно однозначно відображає  множину вершин  степеня k  графа G₁   на  множину вершин  степеня k графа G₂. Тоді ізоморфні графи G₁  і G₂  мають однакову кількість вершин степеня k.

Доведено

Приклад 1.3:

Пари не ізоморфних графів зображені на рис.1.19.

Рис. 1.19.

Ізоморфізм  можна  продовжити  на  множину  маршрутів  графа  аналогічно  тому, як його було продовжено на множину ребер. Маршруту      S = (v₀, v₁, …, v_k) у графі G₁ поставимо у відповідність маршрут φ"(S) =  (φ(v₀),  φ(v₁),  …, φ(v_k))  у графі G₂. Оскільки  φ — ізоморфізм,  вказане відображення  φ"  буде  взаємно однозначним відображенням множини маршрутів G₁  на множину маршрутів G₂. Воно зберігає довжину маршруту,  а також властивості маршруту  бути  простим ланцюгом, повним  простим ланцюгом,  максимальним  простим ланцюгом,  циклом,  простим циклом. З цих міркувань випливає наступна теорема [32, c.20-21].

Теорема  1.6.  В ізоморфних  графах  для довільного  k  (k ≥ 0)  існує взаємно-однозначна відповідність:

1)  між множинами простих  ланцюгів довжини k;

2)  між множинами простих  циклів довжини k.

Висновок  1.6.1. Ізоморфізм зберігає відстань між вершинами графа.

Висновок 1. 6.2. Для зв’язного графа ексцентриситет вершин, діаметр та радіус є інваріантами.

Рівність  інваріантів  є  необхідною  умовою  ізоморфності  графів,  проте  не  є достатньою,  тобто  графи  з  однаковими  значеннями  деяких  інваріантів  не обов’язково  ізоморфні.  Наприклад,  графи  на  рис. 1, в для довільного  k ≥ 0 мають однакові кількості вершин степеня k та однакові кількості простих циклів довжини k, але не є ізоморфними. Проте вершини степеня 3 в них мають різні ексцентриситети [28, c.19].

1.4. Планарність  графів

 

Повернемося до задачі про  три будинки та три колодязі. Її питання в термінах теорії графів можна сформулювати так: чи можна  укласти діаграму графа К_3,3 площині так, щоб лінії, відповідні ребрам, не мали спільних точок, крім вершини, інцидентної їм обом. Для графа К_3,3  відповідь буде “не можна”. Взагалі, можливість укладання графа на площині важлива, коли треба знайти діаграму графа, в якій ребра перетинаються лише в інцидентних їм  вершинах.  Це  питання постає  в задачах,  пов’язаних  з картами доріг, електричними схемами та іншими видами об’єктів.

Уточнимо,  що  означає  “укласти  граф  на  поверхні”.  Кажуть,  що  граф укладається  на  поверхні,  якщо  він  ізоморфний  графу,  вершини  якого  є  точками  поверхні,  а  ребра —  неперервними  лініями  поверхні  без  самоперетинів,  що з’єднують відповідні вершини, причому  жодні два ребра не мають спільних точок, окрім  вершини,  інцидентної  їм  обом  (цей  граф  інколи  називають  укладкою). Аналогічним  є поняття укладання графа  в просторі.