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

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

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

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

 

ПОШУК:   

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

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

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

 

Розкладність графів. Квазіцикли і квазіпромені

 

Послідовність x1,x2,…,xk різних вершин зв'язного графа Gr(V,E)

називається квазіциклом, якщо

 

d(x1,x2)( 3, d(x2,x3)( 3,…, d(xk-1,xk)( 3, d(xk,x1)( 3.

 

В кожному скінченному зв'язному графі існує квазіцикл, що проходить

через кожну його вершину. Це твердження випливає з такої теореми про

квазіцикл.

 

Теорема 1. Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n, n( 2. Для

довільних суміжних вершин x,y ( V існує квазіцикл x1,x2,…,xn , такий що

x=x1, y=xn .

 

Доведення. Оскільки в графі Gr(V,E) є кістяк, в якому вершини x,y теж

суміжні, можна вважати, що Gr(V,E) - дерево. Застосуємо індукцію по n.

Для n=2 твердження очевидне. Приймемо припущення індукції і розглянемо

два випадки.

 

Випадок 1. |B(x,1)|=2, тобто x - кінцева вершина дерева і B(x,1)={x,y}.

Видалимо вершину x і ребро (x,y). Одержимо дерево Gr'(V',E') з множиною

вершин V'=V\{x} і множиною ребер E'=E\{x,y}. Виберемо вершину z, суміжну

з вершиною y в дереві Gr'(V',E') . За припущенням індукції існує

квазіцикл x2,x3,…,xn в дереві Gr', такий що x2=z, xn=y. Тоді x1,x2,

x3,…,xn - квазіцикл в дереві Gr.

 

Випадок 2. |B(x,1)|>2. Якщо |B(y,1)|=1, то заміною пари x,y парою y,x ми

опиняємося у першому випадку. Отже, можна вважати, що |B(x,1)|>1,

|B(y,1)|>1. Видалимо ребро (x,y) і одержимо два дерева Gr1(V1,E1),

Gr2(V2,E2) з коренями x і y. Нехай |V1|=k, |V2|=m. Оскільки k( 2, m( 2,

то за припущенням індукції існують квазіцикли x1,x2,…,xk і y1,y2,…,xm

в деревах Gr1 і Gr2, такі що x1=x, ym=y і (x1,xk)(E1, (y1,ym)(E2 .

Оскільки відстань між xk та y1 в дереві Gr дорівнює 2, то x1,x2,…,xk ,

y1,y2,…,xm - потрібний нам квазіцикл в дереві Gr.

 

Задача 1. Навести приклад скінченного дерева Gr(V,E), для якого не існує

упорядкування x1,x2,…,xn множини вершин V, такого що d(x1,x2)( 2,

d(x2,x3)( 2,…, d(xn-1,xn)( 2. Графи, що допускають подібні упорядкування

вивчаються в наступному параграфі.

 

Застосуємо теорему 1 для побудови деяких розбиттів графів.

 

Теорема 2. Нехай r,n - натуральні числа, r - дільник числа n. Для

кожного зв'язного графа Gr(V,E), |V|=n існує врівноважене розбиття V=V0

( V1 (…(Vr-1 таке що

 

dist(V0,V1)( 3, dist(V1,V2)( 3,…, dist(Vr-2,Vr-1 )( 3, dist(Vr-1, V0 )(

3.

 

Доведення. Для n=1 твердження очевидне. Для n( 2 візьмемо довільні

суміжні вершини x,y. За теоремою 4.1 існує бієкція f: V( {0,1,…,n-1},

така що f(0)=x, f(n-1)=y і d(f(i),f(i+1))( 3 для всіх i( {0,1,…,n-2}.

Для довільної вершини v(V покладемо ((v)=f(v) mod r. Покладемо V0=(

-1(0), V1=( -1(1),…, Vr-1=( -1(r-1).

 

Зауважимо, що індекс кожної підмножини розбиття з теореми 4.2 не

перевищує 3r . Отже, порівняно з теоремою 1.2, теорема 4.2 програє в

оцінці індексу розбиття, але виграє в оцінці відстаней між сусідніми

підмножинами розбиття.

 

Послідовність n(( різних вершин нескінченного зв'язного графа

називається квазіпроменем, якщо d(xn , xn+1)( 3 для всіх n(( . Граф

Gr(V,E) назвемо квазіпроменевим, скорочено qr-графом, якщо існує

квазіпромінь, що проходить через усі вершини цього графа. Якщо в

-----> Page:

0 [1] [2] [3] [4]

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