WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Деякі важливі класи графів: дерева та двочасткові графи - Реферат

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


Реферат на тему:
Деякі важливі класи графів: дерева та двочасткові графи
Граф без циклів називається ациклічним.
Ациклічний зв'язний граф називається деревом.
Довільний ациклічний граф називається лісом.
Очевидно, що зв'язними компонентами лісу є дерева, і тому, кожен ліс може бути зображений у вигляді прямої суми дерев.
Дерева це особливий і дуже важливий клас графів. Особлива роль дерев визначається як широким їхнім застосуванням у різних галузях науки і практики, так і тим особливим положенням, яке дерева займають у самій теорії графів. Останнє випливає з граничної простоти будови дерев. Часто при розв'язуванні різних задач теорії графів їхнє дослідження починають з дерев. Зокрема, порівнюючи нескладною є проблема перевірки ізоморфності дерев.
Існують й інші, рівносильні наведеному, означення дерева, які можна розглядати як характеристичні властивості дерева.
Теорема 3.11. Для графа G =(V,E ), |V |=n, |E |=m такі твердження рівносильні:
1) G дерево (ациклічний зв'язний граф);
2) G зв'язний граф і m =n 1;
3) G ациклічний граф і m = n 1;
4) для будь-яких вершин v і w графа G існує лише один простий ланцюг, що з'єднує v і w ;
5) G ациклічний граф такий, що коли будь-які його несуміжні вершини v i w з'єднати ребром (v,w), то одержаний граф міститиме рівно один цикл.
Доведення. Для доведення теореми покажемо виконання такого ланцюжка логічних слідувань: 1) ==> 2), 2) ==> 3), 3) ==> 4), 4) ==> 5) і 5) ==> 1). Оскільки відношення логічного слідування є транзитивним, то звідси випливатиме рівносильність усіх п'яти тверджень.
Для тривіального графа G (n = 1) справедливість твердження теореми очевидна, тому вважатимемо, що n >1.
1) ==> 2). Доведемо це твердження методом математичної індукції за значенням n.
Для n = 2 умову 1) задовольняє тільки один граф K2, він же задовольняє й умову 2).
Припустімо, що твердження виконується для всіх дерев з кількістю вершин n t (t 2). Розглянемо довільне дерево G =(V,E ), в якому t +1 вершина. Вилучимо з G деяке ребро e E. За теоремою 3.7,б отримаємо граф G , який складається з двох ациклічних зв'язних компонент, тобто з двох дерев T1 і T2. Нехай дерево T1 має n1 вершин і m1 ребер, а дерево T2 n2 вершин і m2 ребер, n1 t і n2 t. За припущенням індукції маємо: m1= n1 1 і m2= n2 1. Отже, для зв'язного графа G виконується
m = m1+ m2 = (n1 1)+(n2 1)+1=n1+n2 1=(t +1) 1= t.
2) ==> 3). Від супротивного. Припустімо, що в графі G є цикл. Вилучивши в G довільне ребро e цього циклу, за теоремою 3.7,а дістанемо зв'язний граф G , в якому n 2 ребра. Останнє суперечить наслідку 3.8.1. Отже, граф G ациклічний.
3) ==> 4). Знову скористаємось методом доведення від супротивного. Припустімо, що для графа G виконується умова 3), але граф G є незв'язний і має k компонент зв'язності. Тоді кожна з цих зв'язних компонент Ti є ациклічною, тобто деревом. Нехай дерево Ti має ni вершин і mi ребер, i=1,2,...,k. З доведеного вище маємо mi = ni 1, i =1,2,...,k. Тоді n 1=m = m1+m2+...+mk=
=(n1 1)+(n2 1)+...+(nk 1)=(n1+n2+...+nk) k = n k. Отже, k = 1 і G є зв'язним графом.
Відтак, припустімо, що граф G задовольняє умову 3), але має дві вершини v і w, які можуть бути з'єднані двома різними простими ланцюгами. Ці ланцюги утворюють циклічний маршрут, що веде з v у v і обов'язково містить у собі деякий цикл (доведіть це самостійно). Останнє суперечить умові 3).
4) ==> 5). Якщо припустити, що в графі G є цикл, тоді будь-які дві вершини цього циклу можуть бути з'єднані між собою принаймні двома простими ланцюгами. Отже, G ациклічний граф. Візьмемо будь-які дві несуміжні вершини v і w у графі G і додамо до нього ребро (v,w); дістанемо граф G . У графі G є один цикл Z, який складається з простого ланцюга, що веде з v у w у графі G, та доданого ребра (v,w). Припустімо, що в графі G є ще один цикл Z1 (Z1 Z). Цикли 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) ==> 1). Необхідно довести, що G зв'язний граф. Припустімо, що це не так. Візьмемо дві довільні вершини v і w з двох різних компонент зв'язності графа G і з'єднаємо їх ребром; дістанемо граф G . Оскільки обидві компоненти є ациклічними графами, то граф G також не міститиме циклів. Це суперечить умові 5).
Теорему 3.11 доведено.
Наслідок 3.11.1. Для довільного дерева T = (V,E ) з n вершинами виконується (v)=2(n 1).
Наслідок 3.11.2. Будь-яке нетривіальне дерево T = (V,E ) має принаймні дві кінцеві вершини.
Припустімо, що дерево T має менше двох кінцевих вершин. Тоді степінь лише однієї вершини може дорівнювати 1, а степені всіх інших вершин не менші 2. Отже, (v) 2(n 1)+1=2n 1, що суперечить наслідку 3.11.1.
Наслідок 3.11.3. Ліс F, який має n вершин і складається з k дерев, містить n k ребер.
Справді, якщо дерево Ti лісу F має ni вершин, то за доведеною теоремою воно містить ni 1 ребро, i =1,2,...,k. Додаючи кількості ребер кожного з дерев Ti, дістанемо число n k ребер в F.
Наслідок 3.11.4. В графі G з n вершинами, який має більше ніж n 1 ребро, є принаймні один цикл.
Розглянемо довільний граф G з n вершинами та кількістю ребер, яка перевищує n 1. Припустімо, що G ациклічний граф. Тоді G ліс, що складається з k дерев (k 1). За попереднім наслідком кількість ребер у такому графі дорівнює n k і
n k > n 1, тобто k <1, що неможливо.
Кістяковим (каркасним) деревом зв'язного графа G =(V,E ) називається дерево T = (V,ET) таке, що ET E.
Кістяковим (каркасним) лісом незв'язного графа G =(V,E ) називається сукупність кістякових (каркасних) дерев зв'язних компонент графа G.
Наслідок 3.11.5. Для зв'язного графа G =(V,E ) можна вказати |E | |V |+1 ребро, після вилучення яких отримаємо кістякове дерево графа G.
Очевидно (див. теорему 3.7), що потрібно послідовно вилучати ребра, які належать циклам [2,7,8]. Порядок вилучення є несуттєвим. Кількість ребер, що залишаться в кістяковому дереві графа G, дорівнює |V | 1, отже, вилученню підлягає
|E | (|V | 1)=|E | |V | +1 ребро.
Наслідок 3.11.6. Нехай граф G =(V,E ) має k компонент зв'язності. Для отримання його кістякового лісу з графа G необхідно вилучити |E | |V |+k ребер.
Для доведення цього твердження потрібно застосувати попередній наслідок до кожної компоненти зв'язності графа G, відтак, підсумувати результати.
Число |E | |V |+k називається цикломатичним числом графа G і позначається (G ).
Пропонуємосамостійно довести такі прості властивості цикломатичного числа (G ) графа G.
Лема 3.3. 1). Для довільного графа G виконується (G ) 0.
2). Граф G є лісом тоді і тільки тоді, коли (G ) = 0.
3). Граф G має рівно один простий цикл тоді і тільки тоді, коли (G )=1.
4). Кількість циклів у графі G не менша ніж (G ).
Алгоритми знаходження кістякових дерев (кістякових лісів) для заданих графів можна побудувати на основі вищезгаданих алгоритмів пошуку вшир або вглиб [2,7,8].
Граф G =(V,E ) називається двочастковим, якщо існує розбиття {V1,V2} множини вершин V на дві підмножини (частки) таке, що для довільного ребра (v,w) E виконується або v V1 i w V2, або v V2 i w V1.
Двочастковий граф G =(V,E ) називається повним двочастковим графом, якщо для будь-якої пари вершин його часток v V1 i w V2 маємо (v,w) E. Якщо |V1|=m i |V2|=n, то повний двочастковий граф G позначається Km,n.
Теорема 3.12 (теорема Кеніга). Граф є двочастковим тоді і тільки тоді, коли всі його цикли мають парну довжину.
Доведення. Необхідність. Нехай G двочастковий граф, а Z цикл графа G. Будь-який маршрут у графі G, що веде з довільної вершини v однієї частки V у будь-яку вершину тієї ж частки, завжди має парну довжину, оскільки всі непарні ребра цього маршруту ведуть з частки V в іншу частку, а всі парні ребра навпаки, повертають маршрут у V . Отже, і довжина циклу Z є парне число.
Достатність. Нехай усі цикли графа G мають парну довжину. Розглянемо довільну зв'язну компоненту G =(V ,E ) графа G. Візьмемо вершину v цієї компоненти і побудуємо розбиття {V1,V2} множини вершин V на дві частки таким чином: віднесемо до V1 всі вершини w V для яких відстань d (v,w) є число парне, а до
V2 всі вершини u V , для яких відстань d (v, u) є число непарне.
Доведемо, що жодні дві вершини з однієї частки не є суміжними в графі G. Припустімо, що v1 і v2 дві різні вершини з однієї частки й існує ребро (v1,v2) E . Тоді жодна з вершин v1 і v2 не збігається з v, оскільки v V1, а всі вершини, суміжні з 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
Loading...

 
 

Цікаве