Способи завдання графа: матрицею інцидентності,

Списком ребер, матрицею суміжності.

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

Розглянемо наступні способи завдання графа :

а) Завдання графа матрицею інцидентності.

Означення. Матрицею інцидентності графа  називається  - матриця , де

Приклад 5.

вешини ребра	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅴ	Ⅵ	Ⅶ
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	1	0	0	0	1	0
6	0	0	1	1	0	0	0
7	0	0	1	0	1	0	0
8	0	0	0	1	0	1	0
9	0	0	0	0	1	0	1
10	0	0	0	0	0	1	1

 

Означення . Матрицею іинцидентності орграфа  називається  - матриця , де

 

    Приклад 6.

                                                                 

вершини ребра	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅴ	Ⅵ	Ⅶ
1	-1	1	0	0	0	0	0
2	-1	0	1	0	0	0	0
3	0	-1	0	1	0	0	0
4	0	1	0	-1	0	0	0
5	0	0	-1	0	1	0	0
6	0	0	-1	0	0	1	0
7	0	0	-1	0	0	0	1
8	0	0	0	1	0	1	2

 

   ³

                  1             ₄                                   

          

                   

₅       

                2                ⁶

                                ₇

                  

      ⁸

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

 

б). Завдання графа списком ребер.

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

    Приклад 7. Задамо списком ребер граф із приклада 5.

 

Ребра	Вершини
1	I, II
2	I, III
3	II, IV
4	I, V
5	II, VI
6	III, IV
7	III, V
8	IV, VI
9	V, VII
10	VI, VII

Приклад 8. Задамо списком ребер граф із приклада 6.

Ребра	Вершини
1	I, II
2	I, III
3	II, IV
4	IV, II
5	III, V
6	III, VI
7	III, VIII
8	VII, VII

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

    в) Завдання графа матрицею суміжності.

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

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

              I II III IV V VI VII

    I    0 1 1 0 1 0 0

    II   1 0 0 1 0 1 0 

    III  1 0 0 1 1 0 0 

    IV  0 1 1 0 0 1 0

    V   1 0 1 0 0 0 1

    VI  0 1 0 1 0 0 1

    VII 0 0 0 0 1 1 0

 

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

                                               I II III IV V VI VII

    I   0 1 1 0 0 0 0

    II  0 0 0 1 0 0 0

    III 0 0 0 0 1 1 1

    IV 0 1 0 0 0 0 0

    V  0 0 0 0 0 0 0

    VI   0 0 0 0 0 0 0

    VII 0 0 0 0 0 0 1

    Матриця суміжності неорієнтованого графа симетрична (тобто ), а орієнтованого - не обов'язково.

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

 

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

    Граф може бути представлений різними способами. Він може бути визначений множинами вершин і ребер, зображений на кресленні, заданий матрицею інцидентності, списком ребер чи матрицею суміжності. Вид креслення залежить від ліній і взаємного розташування вершин, вид матриць і списку ребер залежить від нумерації вершин і ребер. Іноді не так легко зрозуміти, чи однакові графи, задані різними кресленнями чи різними матрицями.

    Означення. Графи  і  називаються ізоморфними, якщо існує взаємно однозначна відповідність між множинами їхніх вершин і множинами їхніх ребер , яка зберігає відношення інцидентності (така, що відповідні ребра з'єднують відповідні вершини).

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

Ізоморфізм графів є відношенням еквівалентності, тобто має властивості рефлексивности, симетричності, транзитивності. Графи розглядаються з точністю до ізоморфізму, тобто розглядаються як класи еквівалентності за відношенням ізоморфізму.

Означення. Числова характеристика, однакова для всіх ізоморфних графів, називається інваріантом графа.

    Приклад. Число вершин p(G) і число ребер q(G) – інваріанти графа G

    Зауваження. Невідомо ніякого набору інваріантів, що визначають граф з точністю до ізоморфізму.

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

 

 

    Як ми відзначали вище (питання 2), граф вважається цілком заданим, якщо нумерація його вершин зафіксована. Ізоморфні графи відрізняються тільки нумерацією вершин. Тому, щоб довідатися, чи задають дві різні матриці суміжності ізоморфні графи, достатньо перевірити, чи подібні ці матриці, чи ні: зробити всілякі перестановки рядків і стовпців першої матриці. Якщо в результаті виникне матриця, яка дорівнює другий, то графи, задані цими матрицями суміжності, ізоморфні.

Матриця інцидентності і список ребер графа залежить від нумерації ребер і вершин. Перехід від однієї пари нумерацій до іншої здійснюється за допомогою перестановок множин вершин і ребер. Щоб довідатися, чи задають різні матриці інцидентності чи списки ребер ізоморфні графи, достатньо перевірити, чи існує такий перехід чи ні.

 

 

Елементи графів

Означення.Граф  називається підграфом графа  (позначається ), якщо  і/або . Якщо  і  і  або , то  називається власним підграфом графа . Якщо , а , то  називається остовним підграфом графа .

Означення. Число ребер, инцидентных вершині , називається ступенем вершини  і позначається :

Мінімальний ступінь вершини графа  позначається :

Максимальний ступінь вершини графа G позначається :

Означення. Якщо ступінь вершини дорівнює 0 ( ), то вершина називається ізольованою. Якщо ступінь вершини дорівнює 1 ( ), то вершина називається кінцевою або висячою.

Означення . В орграфі число дуг, що виходять з вершини, називається напівступенем виходу (позначається ), і вхідних – напівступенем заходу (позначається ).

Теорема (Ейлера). Сума ступенів вершин графа дорівнює подвоєній кількості ребер:

 

 для орграфа

 

Доведення: при підрахунку суми ступенів вершин кожне ребро враховується два рази: для одного кінця ребра і для іншого. ■

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: