Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Лекція № 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.




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

<== попередня сторінка | наступна сторінка ==>
Розфарбовування графа, хроматичний поліном | Основні визначення

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

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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