Деякі важливі класи графів: дерева та двочасткові графи (реферат)

Реферат на тему:

Деякі важливі класи графів: дерева та двочасткові графи

Граф без циклів називається ациклічним.

Ациклічний зв’язний граф називається деревом.

Довільний ациклічний граф називається лісом.

Очевидно, що зв’язними компонентами лісу є дерева, і тому, кожен ліс може бути зображений у вигляді прямої суми дерев.

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

Існують й інші, рівносильні наведеному, означення дерева, які можна розглядати як характеристичні властивості дерева.

Теорема 3.11. Для графа G =(V, E), |V |=n, |E |=m такі твердження рівносильні:

1) G ерево (ациклічний зв’язний граф);

2) G в’язний граф і m =n /p>

3) G циклічний граф і m = n /p>

4) для будь-яких вершин v і w графа G існує лише один простий ланцюг, що з'єднує v і w ;

5) G циклічний граф такий, що коли будь-які його несуміжні вершини v i w з'єднати ребром (v, w), то одержаний граф міститиме рівно один цикл.

Доведення. Для доведення теореми покажемо виконання такого ланцюжка логічних слідувань: 1), 2), 3), 4) і 5). Оскільки відношення логічного слідування є транзитивним, то звідси випливатиме рівносильність усіх п’яти тверджень.

Для тривіального графа G (n = 1) справедливість твердження теореми очевидна, тому вважатимемо, що n >1.

1). Доведемо це твердження методом математичної індукції за значенням n.

Для n = 2 умову 1) задовольняє тільки один граф K2, він же задовольняє й умову 2).

Припустімо, що твердження виконується для всіх дерев з кількістю вершин n (t. Розглянемо довільне дерево G =(V, E), в якому t +1 вершина. Вилучимо з G деяке ребро e За теоремою 3.7,б отримаємо граф G який складається з двох ациклічних зв’язних компонент, тобто з двох дерев T1 і T2. Нехай дерево T1 має n1 вершин і m1 ребер, а дерево T2 вершин і m2 ребер, n1 і n2 За припущенням індукції маємо: m1= n1 і m2= n2 Отже, для зв’язного графа G виконується.

m = m1+ m2 = (n1 (n2 1=n1+n2 t +1) t.

2). Від супротивного. Припустімо, що в графі G є цикл. Вилучивши в G довільне ребро e цього циклу, за теоремою 3.7,а дістанемо зв’язний граф G в якому n ребра. Останнє суперечить наслідку 3.8.1. Отже, граф G ациклічний.

3). Знову скористаємось методом доведення від супротивного. Припустімо, що для графа G виконується умова 3), але граф G є незв’язний і має k компонент зв’язності. Тоді кожна з цих зв’язних компонент Ti є ациклічною, тобто деревом. Нехай дерево Ti має ni вершин і mi ребер, i=1,2,…, k. З доведеного вище маємо mi = ni i =1,2,…, k. Тоді n = m1+m2+…+mk=.

=(n1 (n2 …+(nk (n1+n2+…+nk) = n Отже, k = 1 і G є зв’язним графом.

Відтак, припустімо, що граф G задовольняє умову 3), але має дві вершини v і w, які можуть бути з'єднані двома різними простими ланцюгами. Ці ланцюги утворюють циклічний маршрут, що веде з v у v і обов’язково містить у собі деякий цикл (доведіть це самостійно). Останнє суперечить умові 3).

4). Якщо припустити, що в графі G є цикл, тоді будь-які дві вершини цього циклу можуть бути з'єднані між собою принаймні двома простими ланцюгами. Отже, G циклічний граф. Візьмемо будь-які дві несуміжні вершини v і w у графі G і додамо до нього ребро (v, w) — дістанемо граф G У графі G один цикл Z, який складається з простого ланцюга, що веде з v у w у графі G, та доданого ребра (v, w). Припустімо, що в графі G ще один цикл Z1 (Z1. Цикли Z1 і Z мають спільні ребра (у противному разі Z1 є циклом ациклічного графа G). Якщо серед цих ребер немає ребра (v, w), то знову отримаємо, що Z1 є цикл у графі G. Отже, цикли Z і Z1 мають спільне додане ребро (v, w). Тоді частина циклу Z, що веде з v у w, разом з частиною циклу Z1, що веде з w у v, утворює замкнений (циклічний) маршрут, що веде з v у v у графі G. Зазначені частини циклів Z і Z1 не збігаються, тому цей циклічний маршрут міститиме в собі цикл, що суперечить ациклічності графа G.

5). Необхідно довести, що G в’язний граф. Припустімо, що це не так. Візьмемо дві довільні вершини v і w з двох різних компонент зв’язності графа G і з'єднаємо їх ребромдістанемо граф G Оскільки обидві компоненти є ациклічними графами, то граф G акож не міститиме циклів. Це суперечить умові 5).

Теорему 3.11 доведено.

Наслідок 3.11.1. Для довільного дерева T = (V, E) з n вершинами виконується $$\underset{\mathit{v^IV}}{a}$$ =2(n.

Наслідок 3.11.2. Будь-яке нетривіальне дерево T = (V, E) має принаймні дві кінцеві вершини.

Припустімо, що дерево T має менше двох кінцевих вершин. Тоді степінь лише однієї вершини може дорівнювати 1, а степені всіх інших вершин не менші 2. Отже, $$\underset{\mathit{v^IV}}{a}$$ n 1=2n що суперечить наслідку 3.11.1.

Наслідок 3.11.3. Ліс F, який має n вершин і складається з k дерев, містить n ребер.

Справді, якщо дерево Ti лісу F має ni вершин, то за доведеною теоремою воно містить ni ребро, i =1,2,…, k. Додаючи кількості ребер кожного з дерев Ti, дістанемо число n ребер в F.

Наслідок 3.11.4. В графі G з n вершинами, який має більше ніж n ребро, є принаймні один цикл.

Розглянемо довільний граф G з n вершинами та кількістю ребер, яка перевищує n Припустімо, що G ациклічний граф. Тоді G іс, що складається з k дерев (k. За попереднім наслідком кількість ребер у такому графі дорівнює n і.

n > n тобто k <1, що неможливо.

Кістяковим (каркасним) деревом зв’язного графа G =(V, E) називається дерево T = (V, ET) таке, що ET.

Кістяковим (каркасним) лісом незв’язного графа G =(V, E) називається сукупність кістякових (каркасних) дерев зв’язних компонент графа G.

Наслідок 3.11.5. Для зв’язного графа G =(V, E) можна вказати |E ||+1 ребро, після вилучення яких отримаємо кістякове дерево графа G.

Очевидно (див. теорему 3.7), що потрібно послідовно вилучати ребра, які належать циклам [2,7,8]. Порядок вилучення є несуттєвим. Кількість ребер, що залишаться в кістяковому дереві графа G, дорівнює |V | отже, вилученню підлягає.

|E | | |E | | +1 ребро.

Наслідок 3.11.6. Нехай граф G =(V, E) має k компонент зв’язності. Для отримання його кістякового лісу з графа G необхідно вилучити |E | |+k ребер.

Для доведення цього твердження потрібно застосувати попередній наслідок до кожної компоненти зв’язності графа G, відтак, підсумувати результати.

Число |E | |+k називається цикломатичним числом графа G і позначається).

Пропонуємо самостійно довести такі прості властивості цикломатичного числа) графа G.

Лема 3.3. 1). Для довільного графа G виконується).

2). Граф G є лісом тоді і тільки тоді, коли) = 0.

3). Граф G має рівно один простий цикл тоді і тільки тоді, коли)=1.

4). Кількість циклів у графі G не менша ніж).

Алгоритми знаходження кістякових дерев (кістякових лісів) для заданих графів можна побудувати на основі вищезгаданих алгоритмів пошуку вшир або вглиб [2,7,8].

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

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

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

Доведення. Необхідність. Нехай G вочастковий граф, а Z икл графа G. Будь-який маршрут у графі G, що веде з довільної вершини v однієї частки V будь-яку вершину тієї ж частки, завжди має парну довжину, оскільки всі непарні ребра цього маршруту ведуть з частки V іншу частку, а всі парні ребра авпаки, повертають маршрут у V Отже, і довжина циклу Z є парне число.

Достатність. Нехай усі цикли графа G мають парну довжину. Розглянемо довільну зв’язну компоненту G графа G. Візьмемо вершину v цієї компоненти і побудуємо розбиття {V1,V2} множини вершин V, а дві частки таким чином: віднесемо до V1 всі вершини w ля яких відстань d (v, w) є число парне, а до.

V2 сі вершини u для яких відстань d (v, u) є число непарне.

Доведемо, що жодні дві вершини з однієї частки не є суміжними в графі G. Припустімо, що v1 і v2 дві різні вершини з однієї частки й існує ребро (v1,v2)Тоді жодна з вершин v1 і v2 не збігається з v, оскільки v, а всі вершини, суміжні з v, належать частці V2.

Позначимо через L1 і L2 найкоротші прості ланцюги, що ведуть з v у v1 і v2 відповідно. Довжини цих ланцюгів мають однакову парність, бо, за припущенням, v1 і v2 належать одній частці. Нехай u стання спільна вершина L1 і L2 (починаючи від v). Довжини частин обох цих ланцюгів, що ведуть з u у v1 і з u у v2, також матимуть однакові парності. Тоді маршрут, що складається з частки L1, що веде з u у v1, далі містить ребро (v1,v2) і завершується часткою L2, що веде з v2 в u (тобто проходиться у зворотному порядку) є циклом, довжина якого непарна. Це суперечить умові. Отже, будь-яка зв’язна компонента графа G є двочастковим графом, а тому, і сам граф G є двочастковим.

Наслідок 3.12.1. Граф є двочастковим тоді і тільки тоді, коли він не має простих циклів непарної довжини.

Наслідок 3.12.2. Будь-яке дерево є двочастковим графом.

Наслідок 3.12.3. Простий цикл парної довжини C2k є двочастковим графом.

Список літератури.

1. Харари Т. Теория графов.- М., 1973.

2. Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р.И.- М., 1990.

3. Зыков А. А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р.

Введение

в теорию графов.- М., 1977.

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М., 1978.

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М., 1980.