МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
||||||||||||||||||||||||||||
Лекція № 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 (би і в)). Матриця фундаментальних циклів має два рядки (число циклів) і шість стовпців (число ребер).
У першому рядку матриці одиницями відмічені стовпці з|із| номерами ребер, що входять в перший цикл, а в другому рядку – номери ребер з|із| другого циклу.
Читайте також:
|
|||||||||||||||||||||||||||||
|