Реферат на тему:
Деякі важливі класи графів: дерева та двочасткові графи
Граф без циклів називається ациклічним.
Ациклічний зв’язний граф називається деревом.
Довільний ациклічний граф називається лісом.
Очевидно, що зв’язними компонентами лісу є дерева, і тому, кожен ліс
може бути зображений у вигляді прямої суми дерев.
Дерева ( це особливий і дуже важливий клас графів. Особлива роль дерев
визначається як широким їхнім застосуванням у різних галузях науки і
практики, так і тим особливим положенням, яке дерева займають у самій
теорії графів. Останнє випливає з граничної простоти будови дерев. Часто
при розв’язуванні різних задач теорії графів їхнє дослідження починають
з дерев. Зокрема, порівнюючи нескладною є проблема перевірки
ізоморфності дерев.
Існують й інші, рівносильні наведеному, означення дерева, які можна
розглядати як характеристичні властивості дерева.
Теорема 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 доведено.
?(v)=2(n (1).
Наслідок 3.11.2. Будь-яке нетривіальне дерево T = (V,E ) має принаймні
дві кінцеві вершини.
?(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. Харари Т. Теория графов.- М.,1973. 2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.- М., 1990. 3. Зыков А.А. Основы теории графов.- М., 1987. 4. Оре О. Теория графов.- М., 1980. 5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984. 6. Уилсон Р. Введение в теорию графов.- М., 1977 7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978 8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980
Нашли опечатку? Выделите и нажмите CTRL+Enter
