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

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

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

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

Наслідок 3.6.1. Якщо G незв'язний граф, то граф зв'язний і D()  2.

Справді, якщо G незв'язний граф, то з доведення теореми випливає, що зв'язний і для будь-яких двох вершин v та w графа виконується або d (v,w)=1, або d (v,w)=2.

Доведена теорема дозволяє звести розв'язання деяких важливих проблем теорії графів до випадку зв'язних графів. Зокрема, це стосується проблеми встановлення ізоморфізму заданих графів G1 i G2 (див. теорему 3.2).

Теорема 3.7.Нехай G =(V,E) зв'язний граф і e деяке його ребро. Розглянемо граф G, який отримано з G вилученням ребра e:

а) якщо ребро e належить деякому циклу графа G, то граф Gє зв'язним графом;

б) якщо ребро e не належить жодному циклу графа G, то граф Gне є зв'язним графом і має рівно дві компоненти зв'язності.

Доведення. а) Розглянемо довільні дві вершини v і w графа G.

Якщо маршрут M, що з'єднує вершини v і w у зв'язному графі G, не містить ребра e, то цей же маршрут з'єднуватиме вершини v та w і в графі G. Якщо ж ребро e належить маршруту M і e = (u1,u2), то маршрут, що веде з v у w у графі G, можна побудувати так: беремо маршрут, що веде з v в u1, додаємо до нього ту частину циклу, що містив ребро e, яка залишилась у графі Gі з'єднує вершини u1 і u2; відтак, завершуємо його маршрутом з u2 у w. Отже, граф Gзв'язний.

б) Нехай ребро e = (u1,u2) не належить жодному циклу графа G. Тоді в графі Gвершини u1 та u2 будуть незв'язаними і належатимуть двом різним компонентам зв'язності G1 та G2 графа G. Крім того, у графі Gстануть незв'язаними ті і тільки ті вершини, які були з'єднані в графі G маршрутом, що містив ребро e. Отже, кожна вершина v у Gбуде зв'язаною або з вершиною u1, або з вершиною u2, тобто v належатиме або G1, або G2.

Теорему доведено.

Теорема 3.8. Нехай G =(V,E ) граф з n вершинами і k компонентами зв'язності. Тоді число його ребер m задовольняє такі нерівності: nkm  (nk)(nk +1)/2.

Доведення. Нижню оцінку mnk доведемо індукцією за кількістю ребер у графі G.

Якщо m=0, то очевидно, що n = k і нерівність виконується.

Припустімо, що для всіх графів з числом ребер mt (t  0) відповідна нерівність виконується. Розглянемо граф G з n вершинами і k компонентами зв'язності, який містить t +1 ребро. Вилучимо з графа G довільне ребро. Тоді згідно з теоремою 3.7 отримаємо граф Gз n вершинами, t ребрами і кількістю компонент зв'язності, яка дорівнює k або k +1. За припущенням індукції виконується або tnk, або tn (k +1). Для обох випадків маємо t +1  nk. Отже, бажана нерівність для графа G виконується.

Доведемо верхню оцінку. Розглянемо довільний граф G, що має n вершин, k компонент зв'язності та максимально можливу кількість ребер m. Тоді всі його зв'язні компоненти є повними графами. Нехай Kt і Ks  такі дві компоненти зв'язності графа G, що ts >1. Виконаємо таке перетворення графа G : перенесемо одну вершину v із компоненти Ks у компоненту Kt, тобто вилучимо вершину v з Ks і додамо до Kt, з'єднавши її з усіма вершинами Kt. Дістанемо граф Gз n вершинами, k компонентами зв'язності і кількістю ребер m = m (s 1)+t == m+(ts +1)> m. Остання нерівність суперечить припущенню про максимальність числа ребер у графі G. Отже, шуканий граф з n вершинами, k компонентами зв'язності й найбільшою кількістю ребер має таку структуру: k 1 його компоненти зв'язності є тривіальними графами, а остання компонента є повним графом з nk +1 вершиною. Кількість ребер у такому графі дорівнює (nk)(nk +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...

 
 

Цікаве