РОЗДІЛ 4. ГРАФИ

Дві вершини v_i і v_j Î V графа G = (V, E) називаються суміжними, якщо вони являються граничними вершинами ребра e_k Î E. Відношення суміжності на множині вершин графа можна визначити, представивши кожне ребро як пару суміжних вершин, тобто . Для неорієнтованих графів такі пари неупорядковані, так що , а для орграфів − упорядковані, причому v_i і v_j означають відповідно початкову і кінцеву вершини дуги e_k. Петля при вершині v_i в обох випадках представляється неупорядкованою парою (v_i , v_j). Множина вершин V разом з визначеним на ній відношенням суміжності повністю визначає граф. Граф можна представити матрицею суміжності. Рядки і стовпці цієї матриці відповідають вершинам графа, а її (ij)-елемент дорівнює числу кратних ребер, які зв’язують вершини v_i і v_j (або напрямлених від вершини v_i до вершини v_j для орграфа).

Якщо вершина v_i являється кінцем ребра e_k, то кажуть, що вони інцидентні: вершина інцидентна ребру e_k і ребро e_k інцидентне вершині v_i.

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

Зв’язні ациклічні графи називаються деревами. Нехай множина V деякого дерева містить p вершин, які пронумеровані порядковими числами від 1 доp, тобто V =(1, 2,…, p) . Кожному дереву можна поставити у взаємно-однозначну відповідність деякий символ − упорядковану послідовність p – 2 номерів вершин , серед яких можуть бути і такі, які повторюються, причому . Ця послідовність для даного дерева утворюється наступним чином. Вводиться послідовність N_p(1, 2,…,p). Далі вибирається кінцева вершина з найменшим номером і записується номер a₁ зв’язаної з нею вершини, а сама кінцева вершина видаляється із послідовності N_p(1, 2,…,p). Потім цей процес повторюється доти, доки не буде одержана послідовність . Кожен такий крок відповідає видаленню з дерева кінцевої вершини з найменшим номером і зв’язаного з нею кінцевого ребра, причому через p – 2 кроків від дерева залишиться єдине ребро, положення якого визначається парою номерів вершин, які залишилися в послідовності N_p(1, 2,…,p).

Побудова дерева по його символу виконується послідовним відновленням кінцевих вершин і ребер. На першому кроці із послідовності N_p(1, 2,…,p). вибирається найменший номер , який відсутній в , і будується ребро (a_мін, a₁). Потім видаляється номер із і номер a₁ із a(T) і процес повторюється доти, доки не буде вичерпано символ a(T). Пара вершин, яка залишається в послідовності N_p, визначає останнє ребро дерева.

Питання для самоперевірки

1.Що таке граф, вершина, ребро, дуга?

2.Дайте означення орієнтованого, мішаного графа, псевдографа,

мультиграфа.

3.Що таке частина графа, суграф, підграф?

4.Що таке ейлерів, гамільтонів граф?

5.Що таке планарний граф?

6.Що таке дерево, ліс?

7.Як знаходиться для даного дерева його формула? Як будується дерево за його формулою?

Література: [1], c. 234-255; [2], c. 63-76.

Вправи

79. Побудувати матриці суміжності та інцидентності для графа, зображеного на рис. 4.1.

80. Для дерева, яке задане множиною гілок побудувати дерево і написати його символ: T = {(1, 2), (1, 3), (1, 5), (3, 4), (5, 6), (5, 7), (7, 8), (7, 9)}.

81.Побудувати дерево по його символу T = (1, 3, 1, 1, 3) і послідовності вершин N₇ = (1, 2, 3, 4, 5, 6, 7).

Рис. 4.1. Граф до задачі 79.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
РОЗДІЛ 3. ЛОГІКА ВИСЛОВЛЕНЬ ТА ПРЕДИКАТІВ	\|	ВІДПОВІДІ

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.