UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваДеякі важливі класи графів: дерева та двочасткові графи (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2100
Скачало211
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

 

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

 

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

 

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

може бути зображений у вигляді прямої суми дерев.

 

Дерева ( це особливий і дуже важливий клас графів. Особлива роль дерев

визначається як широким їхнім застосуванням у різних галузях науки і

практики, так і тим особливим положенням, яке дерева займають у самій

теорії графів. Останнє випливає з граничної простоти будови дерев. Часто

при розв’язуванні різних задач теорії графів їхнє дослідження починають

з дерев. Зокрема, порівнюючи нескладною є проблема перевірки

ізоморфності дерев.

 

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

розглядати як характеристичні властивості дерева.

 

Теорема 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

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ