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


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


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


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


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


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


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


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


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


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



Контакти
 


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






Двочасткові графи

Дерева

Деякі класи графів

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

 

Твердження 1. В дереві дві довільні вершини зв’язані єдиним ланцюгом (інакше був би цикл).

Твердження 2.Довільний ланцюг у дереві є простим.

Визначення. У довільному графі G вершина v називається кінцевою, якщо r(v) = 1, тобто існує одне ребро, інцидентне вершині v, і це ребро називається кінцевим.

Твердження 3. У дереві є хоча б дві кінцеві вершини.

Розглянемо дерево G і виберемо довільну вершину v0. Кожному ребру e = (a, b) зіставимо той кінець, який більш віддалений від v0 (оскільки в дереві всі ланцюги є простими, то від довільної вершини до v0 веде лише один ланцюг).

Твердження 4.Для дерева виконується рівність vVvE = 1 (vV - кількість вершин, vE - кількість ребер).

Твердження 5. У дереві кожне ребро суттєве (його вилучення веде до порушення зв’язаності графа).

Визначення. В довільному скінченному зв’язаному графі G циклічний ранг:

g(G) = vEvV + 1.

Твердження. Для довільного скінченного зв’язаного графа G циклічний ранг

g(G) ³ 0

і дорівнює кількості ребер, які необхідно вилучити з G для того, щоб отримати дерево (скелет графа).

Для дерев g(G) = 0.

Дерева використовують для розв’язання такої задачі: необхідно з’єднати „n” міст залізничною колією таким чином, щоб не будувати зайвих ліній. При цьому вважається відомим вартість будівництва колії між двома довільними містами. Таким чином, необхідно побудувати зв’язний граф G, який містить всі задані вершини і для якого повна вартість була б найменшою. Очевидно, що граф G - дерево.

Алгоритм розв’язання.

Вибираємо ребро ei з найменшою вартістю. Отримаємо граф A1 = {e1}. На кожному наступному кроці до Ai 1 додаємо ребро, яке має найменшу вартість серед тих, що залишились, і таке, що граф Ai = Ai 1 È {ei} не має циклів. Останній граф An 1 = G і є шуканим.

 

 

Граф G =(V,E ) називається двочастковим, якщо існує розбиття {V1,V2} множини вершин V на дві підмножини (частки) таке, що для довільного ребра (v,wE виконується або v ÎV1 i w ÎV2, або v ÎV2 i w ÎV1.

Двочастковий граф G =(V,E ) називається повним двочастковим графом, якщо для будь-якої пари вершин його часток v ÎV1 i w ÎV2 маємо (v,wE. Якщо |V1|=m i |V2|=n, то повний двочастковий граф G позначається Km,n.

Теорема (теорема Кеніга). Граф є двочастковим тоді і тільки тоді, коли всі його цикли мають парну довжину.

 

 

Визначення. Нехай G(V1, V2) - дводольний граф. Пароз’єднання – це підмножина ребер графу G:{(xi, yj), …}, де xi Î V1 а yj Î V2, причому жодні два ребра не мають спільних вершин.

Визначення. Максимальне пароз’єднання (П) – це пароз’єднання дводольного графу G, яке має найбільшу кількість ребер.

Розглянемо таку задачу: знайти максимальне пароз’єднання, яке містить всі вершини множини V1.

Твердження (теорема Холла). Максимальне пароз’єднання П дводольного графу покриває всі вершини множин V1 тоді і тільки тоді, якщо для довільної множини U1 Í V1 кількість елементів у множині U2 Í V2, яка містить всі вершини, з’єднані ребром хоча б однією вершиною з U1, не менша від кількості вершин множини U1.

Алгоритм побудови максимального пароз’єднання П.

Будемо вважати, що умови теореми Холла виконані. Задамося довільним пароз’єднанням П0. Якщо воно не охоплює всіх вершин множини V1, то існує x0 : x0Î V1 і x0Ï П0.

Побудуємо

W0 = {x0};

W1 = {y | (x0, y) Î G};

W2 = {x | (x, y) Î П0, y Î W1, x Ï W0};

W3 = {y | (x, y) Î G, x Î W2, y Ï W1};

W4 = {x | (x, y) Î П0, y Î W3, x Ï W0 È W2};

W5 = {y | (x, y) Î G, x Î W4, y Ï W1 È W3};

. . .

 

Зауважимо, що, згідно з побудовою, в множинах W1 і W2, W3 і W4, W5 і W6 і т.д. попарно однакова кількість елементів. Крім того, послідовність вершин Wi не може закінчитись на множині з парним індексом W2k, оскільки для множини

U1 = W0 È W2È … È W2k Í V1

кількість вершин у відповідній множині

U2 = W1 È W3È … È W2k - 1 Í V2

(U2 містить всі вершини графу, які з’єднані ребром хоча б з однією з вершин множини U1) на одиницю більше, що суперечить умові теореми Холла. Тому існує вершина y*:

y* Î W2k - 1 і y* Ï П0.

Тоді існує шлях S, який починається з x0, проходить через вершини множин W1 і закінчується в y* і містить непарну (2k ‑ 1) кількість ребер:

S = {e1, e2, …, e2k - 1},

причому всі парні ребра e2k Î П0.

Нове пароз’єднання П1 будуємо наступним чином:

П1 = П0 \ {e2 È e4 È…È e2k - 2} È {e1 È e2 È…È e2k - 1}.

Пароз’єднання П1 містить на одне ребро і на одну вершину з множини V1 більше ніж П0. Якщо П1 охоплює всі вершини множини V1, то беремо деяку вершину x0 : x0Î V1 і x0Î П1 і т.д.

Приклад

 

 

П0 = {(x1, y1), (x3, y2)}.

1) W0 = (x2); W1 = (y2); W2 = (x3); W3 = (y1); W4 = (x1); W5 = (y4).

e1 = (x2, y2); e2 = (x3, y2); e3 = (x3, y1); e4 = (x1, y1); e5 = (x1, y4).

П1 = {(x2, y2), (x3, y1), (x1, y4)}.

2) W0 = (x4); W1 = (y3, y4).

e1 = (x4, y3).

П = П2 = {(x1, y4), (x2, y2), (x3, y1), (x4, y3)}.


 


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

  1. Henri Matisse- Биография художника на английском.
  2. Биография населенного мира
  3. ДЕМОГРАФИЯ
  4. Дробот В. Изучение биографии писателя в школе.- К., 1988.
  5. Електронно-променеві осцилографи
  6. Електронно-променеві осцилографи
  7. Лекция 1. Векторная графика. Macromedia Flash MX Инструменты и технологии рисования во Flash
  8. Лекція № 13. ОРІЄНТОВАНІ ГРАФИ
  9. ЛИТОЛОГО-СТРАТИГРАФИЧЕСКИИ МЕТОД РАСЧЛЕНЕНИЯ
  10. Плоскі та планарні графи
  11. Світлопроменеві (шлейфові) осцилографи




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

<== попередня сторінка | наступна сторінка ==>
Гамільтонові цикли | Плоскі та планарні графи

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

 

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


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