• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

РОЗДІЛ 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).

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

1. Henri Matisse- Биография художника на английском.
2. IV розділ. Сегментація ринку та вибір цільового сегменту
3. IІI розділ. Аналіз стану маркетингового середовища підприємства
4. V розділ. Товарна політика підприємства
5. VI розділ. Маркетингова цінова політика
6. VII розділ. Маркетингові рішення з розподілу та збуту товару
7. VIII розділ. Маркетингова політика комунікацій
8. А) Роздільне складання таблиць (За підручником Богдановича М.В.)
9. Аварійно-рятувальні підрозділи Оперативно-рятувальної служби цивільного захисту, їх призначення і склад.
10. Актив і пасив балансу складаються також з певних розділів.
11. Активи, що реалізуються повільно (А3) – це статті 2-го розділу активу балансу, які включають запаси та інші оборотні активи (рядки 100 до 140 включно, а також рядок 250).
12. Аналіз бойових дій пожежних підрозділів

Переглядів: 546