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

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

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

Послідовність 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. Відмінність може виникнути лише у випадку 2. Якщо множина S1' незліченна, то розіб'ємо її на зліченні підмножини і для кожної з них побудуємо відповідний квазіпромінь з початком в корені x дерева Gr(V,E).

Теорема 5. Для кожного нескінченного звязного графа Gr(V,E) і кожного натурального числа r існує розбиття V=V0(V1(…(Vr-1, таке що

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

Доведення. Розбиття з доведення теореми 2 застосуємо до кожного квазіпроменя, що виникає в процесі доведення теореми 4.