UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75838
останнє поновлення: 2016-12-03
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваШлях у графі. Зв’язність графів (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2598
Скачало208
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

Маршрутом (або шляхом) у графі 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 ( ( v,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 (V виконується d (v,v)=0.

 

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

будь-яких вершин v,w,  u?V виконується

 

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).

 

{d(v,w)}.

 

Діаметром зв’язного графа G (позначається D (G )) називається

максимальний з усіх ексцентриситетів вершин графа G. Мінімальний з усіх

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ