WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Шлях у графі. Зв’язність графів - Реферат

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


Реферат на тему:
Шлях у графі. Зв'язність графів
Маршрутом (або шляхом) у графі 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
Loading...

 
 

Цікаве