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

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

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

Послідовність x1, x2,…, xk різних вершин зв’язного графа Gr (V, E) називається квазіциклом, якщо.

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

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

Теорема 1. Нехай Gr (V, E) — скінченний зв’язний граф, |V|=n, n Для довільних суміжних вершин x, y існує квазіцикл 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 m то за припущенням індукції існують квазіцикли x1, x2,…, xk і y1, y2,…, xm в деревах Gr1 і Gr2, такі що x1=x, ym=y і (x1,xk) (y1,ym). Оскільки відстань між xk та y1 в дереві Gr дорівнює 2, то x1, x2,…, xk, y1, y2,…, xm — потрібний нам квазіцикл в дереві Gr.

Задача 1. Навести приклад скінченного дерева Gr (V, E), для якого не існує упорядкування x1, x2,…, xn множини вершин V, такого що d (x1,x2) d (x2,x3)…, d (xn-1,xn) Графи, що допускають подібні упорядкування вивчаються в наступному параграфі.

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

Теорема 2. Нехай r, n — натуральні числа, r — дільник числа n. Для кожного зв’язного графа Gr (V, E), |V|=n існує врівноважене розбиття V=V0 1 таке що.

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

Доведення. Для n=1 твердження очевидне. Для nвізьмемо довільні суміжні вершини x, y. За теоремою 4.1 існує бієкція f: V, 1,…, n-1}, така що f (0)=x, f (n-1)=y і d (f (i), f (i+1)) для всіх i, 1,…, n-2}. Для довільної вершини vпокладемо =f (v) mod r. Покладемо V0=(0), V1=(1),…, Vr-1=(r-1).

Зауважимо, що індекс кожної підмножини розбиття з теореми 4.2 не перевищує 3r. Отже, порівняно з теоремою 1.2, теорема 4.2 програє в оцінці індексу розбиття, але виграє в оцінці відстаней між сусідніми підмножинами розбиття.

Послідовність <xn>n різних вершин нескінченного зв’язного графа називається квазіпроменем, якщо d (xn, xn+1)для всіх n. Граф Gr (V, E) назвемо квазіпроменевим, скорочено qr-графом, якщо існує квазіпромінь, що проходить через усі вершини цього графа. Якщо в скінченному зв’язному графі, за теоремою 1, існує квазіцикл, що проходить через усі вершини, далеко не кожен нескінченний зв’язний граф має квазіпромінь, що проходить через усі його вершини. Характеризація локальноскінченних qr-дерев викладена в наступному параграфі. Незважаючи на це, поняття квазіпроменя виявляється досить корисним для побудови розбиттів довільних нескінченних зв’язних графів. Центральними результатами цього параграфу є наступні дві теореми.

Теорема 3. Нехай Gr (V, E) — зліченний зв’язний граф. Тоді існує розбиття A множини вершин V на скінченне або зліченне число підмножин, таке що для кожної підмножини Ap>

(і) граф Gr[A] зв’язний;

(іі) граф Gr[A] є qr-графом.

Доведення. Оскільки кожен звязний граф має кістяк, ми можемо вважати граф Gr (V, E) деревом. Зафіксуємо довільну вершину xі назвемо її коренем. Для кожного натурального числа позначимо через Si множину усіх вершин дерева, відстань від яких до кореня дорівнює i. Позначимо через Si' множину всіх вершин y через які проходить скінченне число шляхів з початком у корені 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} Виберемо довільну вершину y. Якщо S1'=окладемо y=x. За теоремою 4.1 існує квазіцикл x1, x2,…, xk, що проходить через усі вершини звязного графа Gr[X'], такий що x1=x, xk=y. Для продовження цього квазіциклу до квазіпроменя виберемо довільну вершину z', суміжну з вершиною x видалимо всі вершини утвореного квазіцикла і до дерева з коренем z застосуємо рекурсію. Врешті решт ми побудуємо квазіпромінь, що виходить з кореня x, враховуючи при цьому ситуації, що можуть виникнути у випадку 2.

Випадок 2. Множина S1' нескінченна. Нехай S1'={yn: n}. Позначимо через Tn дерево з коренем yn, утворене видаленням ребра (x, yn). Нехай Vn — множина всіх вершин дерева Tn. Покладемо X={x}nVn. Послідовним застосуванням теореми 1 побудуємо квазіпромінь з початком в x, що проходить через всі вершини звязного графа Gr[X].

Як в першому, так і у другому випадках, вже побудовано квазіпромінь з початком у вершині x. Видалимо з дерева всі вершини, через які проходить цей квазіпромінь. Виберемо найменше натуральне число i, для якого підмножина Si'' не увійшла до утвореного квазіпроменя. Зауважимо, що при цьому Si'=Виберемо довільний елемент z', через який не пройшов квазіпромінь, і застосуємо рекурсію до дерева з коренем z.

Теорема 4. Нехай Gr (V, E) — довільний нескінченний зв’язний граф. Тоді існує розбиття A множини V на зліченні підмножини, таке що для кожної підмножини Ap>

(і) граф Gr[A}] зв’язний для деякого елемента x/p>

(іі) граф Gr[A}] є qr-графом з квазіпроменем, що починається з вершини x.

Доведення. Застосуємо схему доведення і позначення теореми 3. Відмінність може виникнути лише у випадку 2. Якщо множина S1' незліченна, то розіб'ємо її на зліченні підмножини і для кожної з них побудуємо відповідний квазіпромінь з початком в корені x дерева Gr (V, E).

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

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

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

Теорема 5. Нехай Gr (V, E) — нескінченний звязний граф. Тоді існує зліченна сім'я {n} розбиттів множини V, така що.

(і) |F|=n+1, diam F для всіх F/p>

(іі) якщо n+1|m+1, то є укрупненням розбиття тобто кожна підмножина розбиття є об'єднанням підмножин розбиття /p>

Доведення. Скористаємося розбиттям A з теореми 4. Для кожної підмножини Aпобудуємо квазіпромінь <xn>n, що проходить через усі вершини підмножини A. Розіб'ємо цей квазіпромінь на відрізки.

{x0,x1,…, xn}, {xn+1,xn+2,…, x2n+1},{x2n+2,x2n+3,…, x3n+2},…

Одержані відрізки оголосимо підмножинами розбиття /p>

Теорема 6. Нехай G — нескінченна група з одиницею e, S — скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, eТоді існує зліченна сім'я розбиттів {n} групи G, така що.

(і) |F|=n+1 і xy-1n для всіх x, yі кожної підмножини F/p>

(іі) якщо n+1|m+1, то є укрупненням розбиття /p>

Доведення. Розглянемо граф Келі Cay (G, S), де x, yтоді і тільки тоді, коли x, yxxy-1Застосуємо теорему 5 до кожної звязної компоненти графа Cay (G, S).

Для подальшого розвитку теми скористаємося відомою теоремою про спільну трансверсаль двох розбиттів [5, теорема 4].

Нехай X — довільна множина, n — натуральне число, розбиття множини X на підмножини потужності n. Тоді існує підмножина Tтака що |T|T=1 для всіх підмножин F F' Підмножина T називається спільною трансверсаллю розбиттів /p>

Теорема 7. Нехай G — нескінченна група з одиницею e, S — скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, eТоді для кожного n існує розбиття G=X0, таке що.

G=S 3nXi=Xi S 3n.

для кожного i1,…, n}.

Доведення. Розглянемо розбиття з теореми 4.6. Покладемо)=0)={F-1: Fn }. До пари розбиттів), 0) застосуємо теорему про спільну трансверсаль і виберемо підмножину X0 таку що |X0 =|X0 1|=1 для всіх Fn (0). Видалимо X0 з групи G, покладемо.

)={FX0: Fn (0)}, 1)={F-1: Fn (1)}.

і до пари розбиттів 1), 1) множини GX0 застосуємо теорему про спільну трансверсаль. Позначимо цю спільну трансверсаль через X1 видалимо підмножину X1 з GX0 і т.д.

Теорема 8. Нехай G — нескінченна група з одиницею e, S — скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, eТоді існує розбиття G= Xn, таке що.

G=S 3Xn=Xn S 3/p>

для всіх n .

Доведення. Застосуємо сім'ю розбиттів {: n } з теореми 4.6. Покладемо A0=A0' ={F-1: F1}. До пари розбиттів A1, A1' множини GX0 застосуємо теорему про спільну трансверсаль і виберемо підмножину X1 X0 таку що |X1=|X11|=1 для всіх F Видалимо X1 з множини GX0 і позначимо.

A2={F (X0: F4}, A2'={F-1: F.

До пари розбиттів A2, A2' множини G (X0 застосуємо теорему про спільну трансверсаль, позначимо цю спільну трансверсаль через X2 і.т.д.

Теорема 9. Нехай G — довільна група, H — скінченна підгрупа групи G, |H|=n+1. Тоді існує розбиття G=X0 таке що G=H Xi=Xi H для всіх i1,…, n}.

Доведення. Розглянемо розбиття групи G на праві та ліві суміжні класи за підгрупою H і до цієї пари розбиттів застосуємо теорему про спільну трансверсаль.

Теорема 10. Нехай G — нескінченна група, H0 — зростаючий ланцюг її скінченних підгруп, |H0|>1. Тоді існує розбиття G= Xn таке що G=Hn Xn = Xn Hn для всіх n.

Доведення. Для кожного n позначимо через та розбиття групи G на ліві та праві суміжні класи по підгрупі Hn. До сім'ї розбиттів { n } застосуємо міркування з доведення теореми 8.

Підмножина X групи G називається великою зліва (справа), якщо знайдеться така скінченна підмножина Fщо G=FX (G=XF). Підмножина X, що одночасно велика зліва і справа, називається великою. А. Белла та В.І. Малихін поставили таке запитання [14].

Чи кожну нескінченну групу можна розбити на дві великі підмножини?

Відповідь на це запитання дає остання теорема цього параграфу.

Теорема 11. Кожну нескінченну групу G можна розбити на зліченне число великих підмножин.

Доведення. Якщо кожна скінченна підмножина групи G породжує скінченну підгрупу, то в групі G існує зростаючий ланцюг H0 скінченних підгруп. В цьому випадку застосовуємо теорему 10. В іншому випадку деяка скінченна підмножина Sпороджує нескінченну підгрупу. Застосовуємо теорему 8.

Задача 2. Довести, що будь-яка сім'я великих зліва підмножин аменабельної (зокрема, абелевої) групи, що попарно не перетинаються, є скінченною або зліченною. Нагадаємо, що група G називається аменабельною, якщо існує міра визначена на всіх підмножинах групи G, така що.

(і) =1;

(іі) …)=)+)+ …+) для довільних підмножин A1, A2, …, An, що попарно не перетинаються;

(ііі))= для довільних gA/p>

Задача 3. Нехай X — довільна нескінченна множина, F (X) — вільна група в алфавіті X. Вказати розбиття групи G на |X| великих зліва підмножин. Вказати розбиття групи G на |X| великих підмножин.

Нехай G — довільна група, X — непорожня підмножина із G. Лівим (правим) індексом підмножини X назвемо найменший кардинал k, для якого знайдеться підмножина F|F|=k, така що G=FX (G=XF). Максимальний серед лівого та правого індексів називається індексом підмножини X.

Задача 4. Нехай G — нескінченна група, |G|=k. Довести, що існує розбиття групи G на k підмножин, лівий індекс кожної з яких <k.

Проблема 1. Нехай G — нескінченна група, |G|=k. Чи можна розбити G на k підмножин, індекс кожної з яких <k ?