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

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

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

Маршрутом (або шляхом) у графі 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 < j), то, викинувши з M ділянку (циклічний маршрут) від vi до vj, отримаємо маршрут M e1, v2,e2,…, vi, ej +1,…, ek, w, який також веде з v у w. Якщо M е простий ланцюг, то процедуру вилучення його внутрішніх циклічних ділянок можна повторити. Врешті-решт отримаємо простий ланцюг, що з'єднує вершини v і w.

Граф, усі ребра якого утворюють простий цикл довжини n, позначається Cn.

Простий цикл довжини 3 називається трикутником.

Граф називається зв’язним, якщо будь-яка пара його вершин може бути з'єднана деяким маршрутом.

Компонентою зв’язності (або зв’язною компонентою) графа G називається його зв’язний підграф такий, що він не є власним підграфом жодного іншого зв’язного підграфа графа G.

Відстанню між вершинами v і w зв’язного графа (позначається d (v, w)) називається довжина найкоротшого простого ланцюга, що з'єднує вершини v і w.

Оскільки кожна вершина графа G =(V, E) з'єднана сама з собою маршрутом довжини 0, то для всіх v виконується d (v, v)=0.

Означена функція відстані задовольняє три аксіоми метрики, тобто для будь-яких вершин v, w, uвиконується.

1) d (v, w) d (v, w)=0 тоді і тільки тоді, коли v = w;

2) d (v, w)=d (w, v);

3) d (v, w) (v, u)+d (u, w).

Справедливість перших двох аксіом очевидна. Доведемо третю аксіому, яка носить назву нерівності трикутника. Нехай v, e1, v2,e2,…, ek, u аршрут з v в u, а u, e12, e2., elаршрут з u у w, тоді послідовність v, e1, v2,e2,…, ek, u, e1,e2., el маршрутом, що веде з v у w і має довжину d (v, u)+d (u, w). Зрозуміло, що цей маршрут не може бути коротшим від найкоротшого маршруту, що веде з v у w, тому.

d (v, w) (v, u)+d (u, w).

Ексцентриситетом e (v) довільної вершини v зв’язного графа G =(V, E) називається найбільша з відстаней між вершиною v і всіма іншими вершинами графа G, тобто e (v)= $$\underset{\mathit{w^IV}}{\text{max}}$$ {d (v, w)}.

Діаметром зв’язного графа G (позначається D (G)) називається максимальний з усіх ексцентриситетів вершин графа G. Мінімальний з усіх ексцентриситетів вершин зв’язного графа G називається його радіусом і позначається R (G).

Вершина v називається центральною, якщо e (v)=R (G). Центром графа G називається множина всіх його центральних вершин.

Вершини v i w графа G називаються зв’язаними, якщо в G існує існує маршрут, що з'єднує v і w.

Відношення зв’язаності Z рефлексивне, транзитивне і симетричне, а значить, є відношенням еквівалентності на множині V. Розглянемо фактор-множину V /Z = {V1,V2,…, Vt }. Підграфи Gi=(Vi, Ei), де Ei=E 2), очевидно, є компонентами зв’язності графа G. Крім того, виконується G = $$\underset{i=1}{\overset{t}{}}{G}_i$$ .

Цей факт можна сформулювати у вигляді такого твердження.

Теорема 3.5. Будь-який граф однозначно зображається у вигляді прямої суми своїх компонент зв’язності.

Якщо граф G зв’язний, то всі його вершини попарно зв’язані, тобто V /Z ={V } i G має єдину зв’язну компоненту, яка збігається із самим графом G.

Теорема 3.6. Для будь-якого графа G =(V, E) або він сам, або його доповнення є зв’язним графом.

Доведення. Якщо G зв’язний граф, то твердження теореми виконується.

Нехай G =(V, E) езв’язний граф і G1=(V1,E1) одна з його компонент зв’язності. Розглянемо графи G1 i G де V V1 і E E1. Для будь-якої пари вершин v i w графі $$\stackrel{}{G}$$ існує ребро (v, w), тому що ці вершини є несуміжні в графі G. Відтак, оскільки для кожної пари вершин v1, v2графа G1 і довільної вершини w снують ребра (v1,w) i (v2,w), які належать множині ребер графа $$\stackrel{}{G}$$, то в графі $$\stackrel{}{G}$$ такі вершини v1 і v2 є зв’язаними. Аналогічно встановлюємо зв’язність у графі $$\stackrel{}{G}$$ будь-якої пари вершин w1 i w2 з множини V Отже, всі пари вершин графа $$\stackrel{}{G}$$ зв’язані між собою.

Наслідок 3.6.1. Якщо G незв’язний граф, то граф $$\stackrel{}{G}$$ зв’язний і D ($$\stackrel{}{G}$$) .

Справді, якщо G незв’язний граф, то з доведення теореми випливає, що $$\stackrel{}{G}$$ зв’язний і для будь-яких двох вершин v та w графа $$\stackrel{}{G}$$ виконується або 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 p>

Якщо маршрут 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 задовольняє такі нерівності: n m (n +1)/2.

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

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

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

Доведемо верхню оцінку. Розглянемо довільний граф G, що має n вершин, k компонент зв’язності та максимально можливу кількість ребер m. Тоді всі його зв’язні компоненти є повними графами. Нехай Kt і Ks акі дві компоненти зв’язності графа G, що t >1. Виконаємо таке перетворення графа G: перенесемо одну вершину v із компоненти Ks у компоненту Kt, тобто вилучимо вершину v з Ks і додамо до Kt, з'єднавши її з усіма вершинами Kt. Дістанемо граф G n вершинами, k компонентами зв’язності і кількістю ребер mm t =.

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

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

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

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

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

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

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

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

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

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

6. Уилсон Р.

Введение

в теорию графов.- М., 1977.

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

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