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

Лекція № 13. ОРІЄНТОВАНІ ГРАФИ

Цикли

Маршрут, в якому почало|розпочало,зачало| і кінець співпадають|збігаються|, – циклічний. Циклічний маршрут називається циклом, якщо він – ланцюг|цеп|.

Остовом|кістяком| графа G називається граф, що не містить|утримує| циклів і що складається з ребер графа G і всіх його вершин. Остов|кістяк| графа визначається неоднозначно.

Ребра графа, що не входять в остов|кістяк|, називаються хордами. Цикл, що виходить при додаванні|добавці| до остову|кістяка| графа його хорди, називається фундаментальним щодо|відносно| цієї хорди.

Теорема 12.11. Число ребер неографа|, які необхідно видалити|знищити,віддалити| для отримання|здобуття| остову|кістяка|, не залежить від послідовності їх видалення|віддалення| і рівно цикломатичному| рангу графа.

Приклад|зразок| 12.8. По заданій матриці суміжності:

,

визначити число циклів довжини 3 () і довжини 4 (). Записати матрицю фундаментальних циклів.

Рішення|розв'язання,вирішення,розв'язування|. Матриця суміжності даного графа симетрична, тому їй відповідає неорієнтований граф. Сума ненульових елементів матриці рівна 12, отже, по лемі про рукостискання в графі 6 ребер. Побудуємо|спорудимо| цей граф (мал. 12.10). Очевидно, в ньому два цикли (3–4–5 і 1–3–5) завдовжки 3 і один цикл (1–3–4–5) завдовжки 4. У даному завданні|задачі| рішення|розв'язання,вирішення,розв'язування| одержане|отримане| прямим підрахунком по зображенню графа. Для складніших випадків існує алгоритм рішення задачі по матриці суміжності.

Відомо, що слід (trace) матриці суміжності, піднесений до k-го|ступеня, рівний числу циклічних маршрутів довжини k (див. теорему 12.4). Це число включає і шукане число циклів. Цикл відрізняється від циклічного маршруту тим, що в ньому не повторюються ребра. Крім того, передбачається|припускається|, що шукані цикли не помічені|позначені|, а в слід матриці входять саме помічені|позначені| маршрути.

Мал. 12.10

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

,

і одержимо|отримаємо|

.

Оскільки циклічних маршрутів завдовжки 3, відмінних|інших| від циклів завдовжки 3, не існує, знайдене число і є відповідь в поставленому завданні|задачі|.

З|із| циклами завдовжки 4 трохи складніше. У слід четвертого ступеня|міри| матриці суміжності графа

,

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

Легко відмітити|помітити|, що . Число залежить від ступенів|мір| вершин, сусідніх :

,

де – ребро, інцидентне вершинам i і k.

Для графа на мал. 12.10 одержимо|отримаємо|

,

,

,

.

З урахуванням того, що непомічених|позначених| циклів завдовжки 4 в 8 разів менше, одержимо|отримаємо|

.

Після|потім| перетворень формула прийме вигляд|вид|

.

Для знаходження матриці фундаментальних циклів пронумеруємо ребра графа, починаючи нумерацію з хорд, як показано на мал. 12.11 (а).

Мал. 12.11

Двом хордам, 1 і 2, відповідають два фундаментальні цикли: 1–4–5 і 2–4–6 (мал. 12.11 (би і в)). Матриця фундаментальних циклів має два рядки (число циклів) і шість стовпців (число ребер).

У першому рядку матриці одиницями відмічені стовпці з|із| номерами ребер, що входять в перший цикл, а в другому рядку – номери ребер з|із| другого циклу.

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

1. Henri Matisse- Биография художника на английском.
2. Биография населенного мира
3. Вид заняття: лекція
4. Вид заняття: лекція
5. Вид заняття: лекція
6. Вид заняття: лекція
7. Вид заняття: лекція
8. Вступна лекція
9. Вступна лекція 1. Методологічні аспекти технічного регулювання у
10. Двочасткові графи
11. ДЕМОГРАФИЯ
12. Дробот В. Изучение биографии писателя в школе.- К., 1988.

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