.

Шлях у графі. Зв’язність графів (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 2772
Скачать документ

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

Шлях у графі. Зв’язність графів

Маршрутом (або шляхом) у графі G =(V,E ) називається послідовність

v1, e1, v2, e2, … , ek, vk +1
(3.2)

вершин vi і ребер ei така, що кожні два сусідні ребра в цій
послідовності мають спільну вершину, отже, ei=(vi,vi +1), i=1,2,…,k.
Вершина v1 називається початком шляху, а вершина vk +1 ( кінцем шляху.
Всі інші вершини цього шляху називаються проміжними, або внутрішніми,
вершинами.

Кількість k ребер у маршруті називається довжиною маршруту. Кажуть, що
цей маршрут з’єднує вершини v1 і vk +1 або веде з вершини v1 у вершину
vk +1.

Маршрутом довжини 0 вважається послідовність, що складається з єдиної
вершини.

Маршрут, в якому всі ребра попарно різні, називається ланцюгом. Маршрут,
в якому всі проміжні вершини попарно різні, називається простим
ланцюгом.

Маршрут (3.2) називається замкненим (або циклічним), якщо v1=vk +1.
Замкнений ланцюг називається циклом, а замкнений простий ланцюг (
простим циклом.

Лема 3.2. Будь-який маршрут, що веде з вершини v у вершину w, містить у
собі простий ланцюг, що веде з v у w.

Доведення. Справді, нехай v,e1,v2,e2,…,ek,w ( маршрут M, що веде з v у
w і такий, що серед його проміжних вершин є однакові. Якщо vi=vj
(i 1. Виконаємо таке
перетворення графа G : перенесемо одну вершину v із компоненти Ks у
компоненту Kt, тобто вилучимо вершину v з Ks і додамо до Kt, з’єднавши
її з усіма вершинами Kt. Дістанемо граф G ( з n вершинами, k
компонентами зв’язності і кількістю ребер m( = m ((s (1)+t   =

= m+(t (s +1)> m. Остання нерівність суперечить припущенню про
максимальність числа ребер у графі G. Отже, шуканий граф з n вершинами,
k компонентами зв’язності й найбільшою кількістю ребер має таку
структуру: k (1 його компоненти зв’язності є тривіальними графами, а
остання компонента є повним графом з n (k +1 вершиною. Кількість ребер у
такому графі дорівнює

(n ( k)(n ( k +1)/2 (див. лему 3.1).

Наслідок 3.8.1. Довільний зв’язний граф з n вершинами містить не менше
ніж n (1 ребро.

Наслідок 3.8.2. Якщо в графі G з n вершинами кількість ребер більша ніж
(n (1)(n (2)/2, то граф G зв’язний.

Список літератури

1. Харари Т. Теория графов.- М.,1973.

2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов
В.И., Тышкевич Р.И.- М., 1990.

3. Зыков А.А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р. Введение в теорию графов.- М., 1977

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020