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 < j), то, викинувши з M ділянку (циклічний маршрут) від vi до vj, отримаємо маршрут Mv,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, то для всіх vV виконується d (v,v)=0.

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

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

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

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

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

Ексцентриситетом e(v) довільної вершини v зв'язного графа G =(V,E ) називається найбільша з відстаней між вершиною v і всіма іншими вершинами графа G, тобто e(v)={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=EVi(2), очевидно, є компонентами зв'язності графа G. Крім того, виконується G =.

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

Теорема 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,E ), де V=V V1 і E=E E1. Для будь-якої пари вершин vV1 i wVу графі існує ребро (v,w), тому що ці вершини є несуміжні в графі G. Відтак, оскільки для кожної пари вершин v1,v2V1 графа G1 і довільної вершини wVіснують ребра (v1,w) i (v2,w), які належать множині ребер графа , то в графі такі вершини v1 і v2 є зв'язаними. Аналогічно встановлюємо зв'язність у графі будь-якої пари вершин w1 i w2 з множини V. Отже, всі пари вершин графа зв'язані між собою.

Loading...

 
 

Цікаве