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

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

ГоловнаМатематика, Геометрія, Статистика → Розкладність графів. Квазіцикли і квазіпромені - Реферат

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


Реферат на тему:
Розкладність графів. Квазіцикли і квазіпромені
Послідовність 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-графом, якщо існує квазіпромінь, що проходить через усі вершини цього графа. Якщо в скінченному зв'язному графі, за теоремою 1, існує квазіцикл, що проходить через усі вершини, далеко не кожен нескінченний зв'язний граф має квазіпромінь, що проходить через усі його вершини. Характеризація локальноскінченних qr-дерев викладена в наступному параграфі. Незважаючи на це, поняття квазіпроменя виявляється досить корисним для побудови розбиттів довільних нескінченних зв'язних графів. Центральними результатами цього параграфу є наступні дві теореми.
Теорема 3. Нехай Gr(V,E) - зліченний зв'язний граф. Тоді існує розбиття A множини вершин V на скінченне або зліченне число підмножин, таке що для кожної підмножини A A
(і) граф Gr[A] зв'язний;
(іі) граф Gr[A] є qr-графом.
Доведення. Оскільки кожен звязний граф має кістяк, ми можемо вважати граф Gr(V,E) деревом. Зафіксуємо довільну вершину x V і назвемо її коренем. Для кожного натурального числа позначимо через Si множину усіх вершин дерева, відстань від яких до кореня дорівнює i. Позначимо через Si' множину всіх вершин y Si, через які проходить скінченне число шляхів з початком у корені x, Si''= Si Si'. Розглянемо два випадки.
Випадок 1. Множина Si' скінченна. Нехай Si'={y1,y2,…,yn}. Позначимо через T1, T2,…,Tn дерева з коренями y1,y2,…,yn, що утворюються після видалення вершини x і ребер (x,y1), (x,y2),…,(x,yn). Позначимо через V1,V2,…,Vn множини вершин дерев T1, T2,…,Tn і покладемо X={x} V1 V2 … Vn. Виберемо довільну вершину y S1'. Якщо S1'= покладемо y=x. За теоремою 4.1 існує квазіцикл x1,x2,…,xk , що проходить через усі вершини звязного графа Gr[X'], такий що x1=x, xk=y. Для продовження цього квазіциклу до квазіпроменя виберемо довільну вершину z S1'', суміжну з вершиною x видалимо всі вершини утвореного квазіцикла і до дерева з коренем z застосуємо рекурсію. Врешті решт ми побудуємо квазіпромінь, що виходить з кореня x, враховуючи при цьому ситуації, що можуть виникнути у випадку 2.
Випадок 2. Множина S1' нескінченна. Нехай S1'={yn: n }. Позначимо через Tn дерево з коренем yn, утворене видаленням ребра (x,yn). Нехай Vn - множина всіх вершин дерева Tn. Покладемо X={x} n Vn. Послідовним застосуванням теореми 1 побудуємо квазіпромінь з початком в x, що проходить через всі вершини звязного графа Gr[X].
Як в першому, так і у другому випадках, вже побудовано квазіпромінь з початком у вершині x. Видалимо з дерева всі вершини, через які проходить цей квазіпромінь. Виберемо найменше натуральне число i, для якого підмножина Si'' не увійшла до утвореного квазіпроменя. Зауважимо, що при цьому Si'= . Виберемо довільний елемент z Si'', через який не пройшов квазіпромінь, і застосуємо рекурсію до дерева з коренем z.
Теорема 4. Нехай Gr(V,E) - довільний нескінченний зв'язний граф. Тоді існує розбиття A множини V на зліченні підмножини, таке що для кожної підмножини A A
(і) граф Gr[A {x}] зв'язний для деякого елемента x V;
(іі) граф Gr[A {x}] є qr-графом з квазіпроменем, що починається з вершини x.
Доведення. Застосуємо схему доведення і позначення теореми 3. Відмінність може виникнути лише у
Loading...

 
 

Цікаве