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

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

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

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

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

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

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

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

Теорема 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, що неможливо. Кістяковим (каркасним) деревом зв’язного графа 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

Похожие записи