загрузка...
загрузка...
На головну

Доповнення. дерева

Дивіться також:
  1. Дерева. Теорема про еквівалентних визначеннях дерева.

Рис 6. Зв'язні і незв'язні графи.

Рис 5. Стандартні неплоскі графи.

Рис 4. Редукція графів.

Рис 3. Плоский граф.

V

Затвердження 3.Композиція ізоморфізмів і зворотне ізоморфізму відображення самі є ізоморфізм.

Теорема 2. Наступні величини і властивості є інваріантами графа , тобто зберігаються при ізоморфизмах:

1). - чісловершін графа;

2). - чіслоребер і дуг графа;

3). - число дуг графа;

4). - чіслоребер графа;

5). - чіслоціклов в графі;

6). - чіслоконтуров в графі;

7). - чіслопетель в графі;

8). - чіслолістьев в графі;

9). - чісловершін графа ступеня ;

10). - чісловершін графа полустепені заходу ;

11). - чісловершін графа полустепені результату ;

12). Можливості підключення графа;

13). Ейлерову, Гамільтонових і планарність графа;

Визначення 27. Редукцією графа називається «стирання» вершини ступеня .



 редукція

Затвердження 4.Якщо скороченої граф не плаский, то і сам граф неплоский.

Затвердження 5.Якщо підграф не плаский, то і сам граф неплоский.

Теорема 3. Граф не є плоским тоді і тільки тоді, коли за допомогою операцій переходу до подграфа і редукції він зводиться до одного з двох стандартних неплоских графів .


       
   
 


Визначення 28. Граф називається дводольним, якщо безліч його вершин можна розбити на два таких непересічних безлічі (частки), що и (де - Порожня множина), причому - Суміжні тільки, якщо , а або навпаки . Якщо при цьому кожна вершина безлічі з'єднана з кожною вершиною безлічі , То двочастковий граф називається повним дводольним графом.

Граф - Повний двочастковий, а - Просто повний.

Визначення 29. Граф називається зв'язковим, якщо будь-які дві вершини можна з'єднати деякої ланцюгом.


Зв'язний Незв'язний.


Визначення 30. Зв'язкова компонента графа - це максимальний зв'язний підграф.


Рис 7.

       
 
   
 


- Зв'язкові компоненти.

       
   


Теорема 4. Кожна вершина графа міститься в деякій зв'язковий компоненті.

Доведення. Візьмемо вершину графа і всі вершини, з якими дану вершину можна з'єднати ланцюгом. Отримаємо частина графа, яка і буде компонентою.

Визначення 31. Мережею називається зв'язний орієнтований граф без петель і циклів.

Вершини з полустепені заходу , Називаються входами, і з полустепені результату , Називаються виходами.

Визначення 32. Кажуть, що дуга спрямована від входу до виходу, якщо вона лежить на деякому шляху від деякого входу до деякого виходу.

Теорема 5.Кожна мережа містить як входи, так і виходи, причому кожна дуга мережі орієнтована від входу до виходу.

Доведення. нехай - Вершина мережі. або - Вихід, або існує така вершина і дуга , що . або - Вихід, або існує така вершина і дуга , що , І т. Д. В силу кінцівки графа отримуємо кінцеву ланцюжок вершин , Яка обривається на вершині , Що є, очевидно, виходом. Аналогічно доводиться існування хоча б одного входу мережі. якщо - Дуга мережі, то від починається ланцюг, що закінчується виходом і в закінчується деяка ланцюг, що починається на вході. Таким чином, поєднуючи обидві ланцюга дугою отримуємо ланцюг від входу до виходу, що містить . Теорема доведена.

Визначення 33. Деревом називається зв'язний неорієнтований граф без петель і циклів (в якому виділена одна вершина, яка називається коренем дерева).

Теорема 6. Нехай- Зв'язний неорієнтований граф з виділеної вершиною. Тоді такі властивості еквівалентні:

1). - Дерево;

2). В графі немає простих циклів (зокрема петлі);

3). Будь-які дві вершини графа пов'язані єдиною простий ланцюгом;

4). Число ребер на 1 менше числа вершин: = - чісловершін графа.

Визначення 34. Рівень кореня за визначенням дорівнює нулю. Число ребер ланцюга, що з'єднує вершину з коренем називається рівнем вершини. Висотою дерева називається максимальний рівень його вершин.

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


Рис 8. Дерево.- корінь


       
   


На малюнку 8 зображено дерево висоти (глибини) 3. Вершини и - Першого рівня, вершини , , - Другого рівня, , , , - Третього рівня (листя).

Лекція № 2. Введення в теорію графів (продовження). «-- попередня | наступна --» ТЕМА. ВСТУП В КУРС
загрузка...
© om.net.ua