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

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

Розкладність графів. Квазігамільтонові Графи Скінченний зв’язний граф Gr (V, E) з множиною вершин V=V (Gr) і множиною ребер E=E (Gr), називається гамільтоновим, якщо існує така нумерація f: {1,2,…, n}множини його вершин, що.

d (f (1), f (2))=d (f (2), f (3))=…=d (f (n-1), f (n))=d (f (n), f (1))=1.

При цьому послідовність f (1), f (2),…, f (n) називається гамільтоновим циклом. Задача характеризації гамільтонових графів — одна з найвідоміших нерозв’язаних проблем теорії графів (див. [5, стор. 85], [12, стор. 72]).

За теоремою 4.1 множину вершин довільного скінченного звязного графа Gr (V, E) можна занумерувати f: {1,2,…, n}так, що.

d (f (1), f (2))d (f (2), f (3))…, d (f (n-1), f (n))d (f (n), f (1))/p>

Послідовність вершин f (1), f (2),…, f (n) називається повним квазіциклом графа. У зв’язку з цим твердженням природно виникають такі означення і проблеми.

Означення 1. Нумерацію f: {1,2,…, n}множини вершин скінченного зв’язного графа Gr (V, E) назвемо квазігамільтоновим циклом (скорочено qh-циклом), якщо.

d (f (1), f (2)) d (f (2), f (3)) …, d (f (n-1), f (n)) d (f (n), f (1)) /p>

Граф, що допускає таку нумерацію вершин назвемо квазігамільтоновим графом (скорочено qhc-графом).

Означення 2. Нумерацію f: {1,2,…, n}множини вершин скінченного зв’язного графа Gr (V, E) назвемо квазігамільтоновим шляхом (скорочено qh-шляхом), якщо.

d (f (1), f (2))d (f (2), f (3))…, d (f (n-1), f (n))/p>

Граф, що допускає таку нумерацію вершин, назвемо qhp-графом.

Проблема 1. Охарактеризувати qhc-графи.

Проблема 2. Охарактеризувати qhp-графи.

В цьому параграфі проблеми 1 та 2 розв’язано для дерев, доведено аналог теореми Дірака для для qhc-графів, а також розглянуто деякі варіанти проблеми 2 для нескінченних графів.

Нехай T (V, E) — скінченне дерево, xB (x, 1)={x, y1, y2,…, ym}. Після видалення вершини x і ребер {x, y1}, {x, y2},…, {x, ym} дерево T розпадається на дерева $$T_{y_1}$$, $$T_{y_2}$$, …, $$T_{y_m}$$ з коренями y1, y2 ,…, ym. Множину цих дерев позначимо ={ $$T_{y_1}$$, $$T_{y_2}$$, …, $$T_{y_m}$$ }.

Лема 1. Нехай T (V, E) — скінченне дерево,.

x={ $$T_{y_1}$$, $$T_{y_2}$$, … $$T_{y_k}$$, $$T_{y_{k+1}}$$ ,…, $$T_{y_m}$$ },.

$$T_{y_1}$$)1, $$T_{y_2}$$)1, …, $$T_{y_k}$$)1, $$T_{y_{k+1}}$$). = $$T_{y_m}$$).

Якщо T — ghc-граф, то k/p>

Доведення. Припустимо супротивне kі зафіксуємо gh-цикл x=x0, x1, x2, …, xn-1 в дереві T. 3 послідовності x0, x1, x2, …, xn-1 викреслимо всі вершини, що не належать множині V ($$T_{y_1}$$) $$T_{y_2}$$) ($$T_{y_3}$$). Одержану послідовність позначимо z1, z2, …, zs. Припустимо для визначеності, що z1$$T_{y_1}$$). Якщо z1=y1, то необхідно z2, z3,., zs $$T_{y_1}$$). Отже, z1 Виберемо максимальний індекс t2,…, s}, такий що zt$$T_{y_1}$$). Очевидно, що zt=y1 і z1, z2, …, zt$$T_{y_1}$$). Припустимо для визначеності, що zt+1$$T_{y_2}$$). Тоді необхідно zt+1=y2 і zt+1, …, zs $$T_{y_2}$$). Одержано суперечність з умовою.

V ($$T_{y_3}$$), z2, …, zs}.

Теорема 1. Скінченне дерево T (V, E) являється qhc-деревом, тоді і тільки тоді, коли існує такий шлях x0, x1, …, xd, що всі вершини з множини V { x0, x1, …, xd} є кінцевими вершинами дерева.

Доведення. Необхідність. Нехай d — діаметр дерева, тобто відстань між двома найбільш віддаленими його вершинами x0, xd. Позначимо через x0, x1, …, xd найкоротший шлях від x0 до xd. Тоді.

B (x0,1)={x0,x1}, B (xd, 1)={xd-1, xd}.

і кожна вершина з множин.

B (x1,1){x0,x1,x2}, B (xd-1,1){xd-2,xd-1,xd}.

є кінцевою. Візьмемо довільний індекс i3,…, d-2}. Оскільки.

i-1,1) 3, i+1,1)/p>

то за лемою 5.1 кожна вершина з множини B (xi, 1){xi-1,xi, xi+1} є кінцевою вершиною дерева.

Достатність. Для d=0 теорема очевидна: будь-яка нумерація множини V є qh-циклом. Припустимо, що d>0 і індукцією по d доведемо існування qh-циклу z0, z1,…, zn-1, такого що z0=x0, z1=x1. Можна вважати, що в умові теореми x0, xd-кінцеві вершини дерева. Для d=1 покладемо z0=x0, z1=x1. Нехай d>1 і B (x1,1)={x0,x1,x2,y1,y2,…ym}. Видалимо вершини x0, y1,y2,…ym і ребра {x0,x1}, {x1,y1}, {x1,y2},… {x1,ym}. Одержимо дерево T шляхом x1, x2,…, xd, що задовольняє умову теореми. За припущенням індукції в Tснує qh-цикл V1, V2, … Vs, такий що v1=x1, v2=x2. Тоді.

x1, x0, y1, y2,…ym, v2, v3, … vs ;

qh-цикл в дереві T, що задовольняє індуктивному припущенню.

Задача 1. Довести, що дерево T є гамільтоновим графом тоді і тільки тоді, коли V (T)=1 або V (T)=2.

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

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

Нехай Gr (V, E) — скінченний зв’язний граф, |V|=n. Якщо |B (x, 1)|ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >n2 +1 для будь-якої вершини xто за теоремою Дірака [5, стор. 74] граф Gr (V, E) є гамільтоновим. Ми доведемо достатню ознаку квазігамільтоновості графа, що є аналогом цієї теореми Дірака.

Теорема 5.2. Нехай Gr (V, E) — скінченний зв’язний граф, |V|=n. Якщо |B (x, 2)|ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >n2 +1 для будь-якої вершини xто граф Gr (V, E) є квазігамільтоновим.

Доведення. Серед послідовностей y1, y2,…, yk різних вершин графа з умовою d (y1,y2)d (y2,y3)…, d (yk-1,yk)виберемо послідовність x1, x2,…, xt максимальної довжини. Очевидно, що B (x1,2), x2,…, xt}, B (xt, 2), x2, …, xt}. Оскільки tі |B (x1,2)|ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >n2 +1, |B (xt, 2)|ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >n2 +1, то знайдуться такі вершини xi, xi+1, i2,…, t-1} що xi+11,2), xit, 2). Перенумеруємо вершини x1, x2,…, xt в такому порядку.

x1,xi+1,xi+2,…, xt, xi, xi-1,…, x2 .

Запишемо цю послідовність як z1, z2,…, zt і помітимо, що.

d (z1,z2)d (z2,z3)…, d (zt-1,zt)d (zt, z1)/p>

Припустимо, що t<n і виберемо вершину xz1, z2 ,…, zt} і вершину zj, j2,…, t} так, що d (zj, x)=1. Тоді відстань між сусідніми вершинами послідовності x, zj, zj+1,., zt, z1, z2,., zj-1 не перевищує 2, що суперечить максимальності t. Отже, t=n і z1, z2,., zn — qh-цикл в графі Gr (V, E).

Загальну проблему 1 характеризації квазігамільтонових графів можна послабити до серії проблем про достатні ознаки квазігамільтоновості. Ось лише дві з них.

Проблема 3. Чи кожен ейлерів граф є квазігамільтоновим? Нагадаємо, що звязний граф називається ейлеревим, якщо локальний степінь кожної його вершини є парним числом.

Проблема 4. Чи кожен планарний граф є квазігамільтоновим?

Вершину x qhc-графа Gr (V, E) назвемо особливою, якщо існує qh-цикл x1, x2,…, xn в Gr, такий що x=x1 і d (x1,x2)=1. Якщо V={x}, то також вважаємо вершину x особливою. З доведення достатності в теоремі 5.1 випливає, що кожне qhc-дерево має особливу вершину. Для конструктивного описання qhp-дерев введемо дві операції приєднання.

Операція А. Нехай Gr1(V1,E1) — qhp-граф з qh-шляхом y1, y2,…ym. Візьмемо довільний qhc-граф Gr2(V2,E2), V1 особливою вершиною x і qh-циклом x=x1,x2,…, xn, d (x1,x2)=1. Побудуємо новий граф Gr (V1E), де E=E1m, x1)}. Зауважимо, що послідовність вершин.

y1, y2, …, ym, x2, x1, xn, xn-1, …, x3.

є qh-шляхом в графі Gr. Отже, в результаті операції приєднання, А отримано новий qhp-граф Gr. Крім того, якщо Gr1, Gr2-дерева, то Gr — теж дерево.

Операція В. Нехай Gr (V, E) — qhp-граф з qh-шляхом y1, y2,…ym. Візьмемо довільну вершину yt, таку що d (y1,yt)=1. Виберемо довільний елемент xі розглянемо граф Gr, Eде E, yt)}. Відмітимо, що послідовність.

x, y1, y2,…, yt, yt+1, …, ym.

є qh-шляхом в графі GrОтже, в результаті операції приєднання В отримано новий qhp-граф GrКрім того, якщо граф Gr був деревом, то Grеж дерево.

Теорема 3. Скінченне дерево T (V, E) являється qhp-графом тоді і тільки тоді, коли T (V, E) є qhc-деревом, або T (V, E) можна отримати з деякого qhc-дерева послідовним застосуванням операцій А, В приєднання qhc-дерев.

Доведення. Достатність випливає з означення операцій приєднання, А і В. Для доведення необхідності зафіксуємо деякий qh-шлях y1, y2,…, ym в дереві T (V, E) і розглянемо два випадки.

Випадок 1: Вершина y1 не є кінцевою вершиною дерева T (V, E). Виберемо максимальний індекс t2,…, m}, такий що d (y1,yt)=1. Позначимо через $$T_{y_1},T_{y_t}$$ дерева з коренями y1, yt, одержані видаленням з дерева T (V, E) ребра {y1,yt}. Якщо t=m, то T (V, E) — qhc-граф. Припустимо, що t<m. Очевидно, що {yt+1,…, ym}$$T_{y_1}$$)=Значить, $$T_{y_t}$$ є qhp-графом з qh-шляхом yt, yt+1,…, ym. Крім того V ($$T_{y_1}$$)={y1,y2,…, yt-1}, d (y1, yt-1)=1. Отже, $$T_{y_1}$$ — qhc-дерево з особливою точкою y1. Залишилось помітити, що T (V, E) можна одержати операцію приєднання, А до $$T_{y_t}$$ графа $$T_{y_1}$$ .

Випадок 2: Вершина y1 є кінцевою вершиною дерева T (V, E). Виберемо індекс t2,…, m} так, що (y1,yt)Позначимо через $$T_{y_t}$$ дерево з коренем yt, одержане видаленням з T (V, E) ребра (y1,yt). Ясно, що V ($$T_{y_t}$$)={y2, y3,…, yt,…, ym} і $$T_{y_t}$$ — qhp-граф з qh-шляхом y2, y3,…, yt, yt+1 ,…, ym. Якщо t=2, то T (V, E) можна отримати з $$T_{y_t}$$ за допомогою операції А. Якщо ж t >2, то T (V, E) можна отримати з $$T_{y_t}$$ за допомогою операції В.

Нагадаємо, що нескінченний зв’язний граф Gr (V, E) називається qr-графом, якщо існує бієкція f: V, така що d (f (i), f (i+1))для будь-якого i.

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

Стовбуром нескінченного дерева T (V, E) називається ін'єктивна послідовність {xn:n} його вершин, що задовольняє такі умови.

(і) d (xn, xn+1)=1 для всіх n;

(іі) після видалення вершин {xn:n} дерево T (V, E) розпадається на скінченні дерева.

Зауважимо, що не кожне нескінченне локально скінченне дерево має стовбур, але за лемою Кьоніга в кожному нескінченному локально скінченному дереві існує ін'єктивна послідовність вершин, що задовольняє умову (і).

Теорема 4. Нескінченне локально скінченне дерево T (V, E) являється qr-графом тоді і тільки тоді, коли T (V, E) має стовбур.

Доведення. Необхідність. Нехай {xn:n} - ін'єктивна послідовність вершин з умовою d (xn, xn+1)=1, n. Позначимо через U множину усіх вершин з V{xn:n}, суміжних з вершинами множини {xn:n}. Для кожної вершини yпозначимо через Ty дерево з коренем y, одержане видаленням ребра (y, xm), де xm — вершина, суміжна з y. Припустимо, що знайдеться вершина zтака що дерево Tz нескінченне. Знайдемо вершину xi, для якої {xi, z}За умовою теореми існує така нумерація {vn:n} вершин дерева T (V, E), що d (vn, vn+1)для всіх n. Виберемо індекс s так, щоб B (xi, 3), v2,…, vs}. Оскільки дерево Tz нескінченне, то знайдеться індекс t>s, такий що vt Тоді.

{vt, vt+1, …}n: n}=p>

Одержано суперечність з тим, що послідовність {vn:n} пробігає всю множину вершин V.

Достатність. Нехай {xn:n} - стовбур дерева T (V, E). Позначимо через T0 дерево з коренем x0, одержане видаленням з T (V, E) ребра {x0,x1}. Для кожного n, n>0 позначимо через Tn дерево з коренем xn, одержане видаленням ребер {xn-1,xn}, {xn, xn+1}. Якщо |V (Tn)|=1, покладемо xn. Якщо ж |V (Tn)|>1, зафіксуємо довільну вершину xnV (Tn), суміжну з вершиною xn. Позначимо kn=|V (Tn)|, n. За теоремою 4.1 існують бієкції.

f0:{1,2,…, k0}0), f0 (x0, f0 (x0)=k0,.

f1:{k0+1,k0+2,…, k0+k1}1), f1 (x10+1, f1 (x1)=k0+k1,.

f2:{k0+k1+1,k0+k1+2,…, k0+k1+k2}2), f2(x20+k1+1, f2(x2)=k0+k1+k2,.

…

що задовольняють умови.

d (fn (i), fn (i+1))p>

для всіх n, i+k1+…+kn-1+1, k0+k1+…+kn}.

Визначимо бієкцію f:{1,2,…}за правилом f (i)=fn (i) тоді і тільки тоді, коли i попадає в область визначення функції fn. Оскільки відстань в графі T (V, E) між вершинами xn та xnе перевищую 2, то f — шукана нумерація.

Проблема 5. Охарактеризувати qr-дерева.

Наведемо одну необхідну і одну достатню ознаки qr-дерева.

Вершину x зв’язного графа Gr (V, E) назвемо вершиною локальної скінченності (локальної нескінченності), якщо куля B (x, 1) скінченна (нескінченна).

Теорема 5. Нехай T (V, E) — qr-дерево, x, y x1, x2, …, xn — найкоротший шлях від x до y, x=x1 y=xn. Позначимо через Tx, Ty дерева з коренями x, y, одержані видаленням ребер {x, x1}, {xn-1,y}. Якщо дерева Tx, Ty нескінченні, то x2, x3,…, xn-1 — вершини локальної нескінченності.

Доведення. Візьмемо квазіпромінь {vn: n}, що проходить через усі вершини дерева. Досить довести, що xn-1 — вершина локальної нескінченності і застосувати індуктивні міркування. Припустимо супротивне: куля B (xn-1,1) скінченна. Виберемо найменше натуральне число t, таке що.

B (xn-1,1)0, v1, …, vt}, vt, y .

Тоді {vt+1, vt+2 ,…}= що суперечить нескінченності дерева Tx.

Теорема 6. Якщо всі некінцеві вершини зліченного дерева T (V, E) є вершинами локальної нескінченності, то T (V, E) — qr-дерево.

Доведення. Нехай {vn: n} - нумерація вершин дерева. Квазіпромінь {yn: n}, що проходить через усі вершини дерева, побудуємо індуктивно. Покладемо y0=v0. Припустимо, що вже визначено відрізок {y0,y1,…, yk} квазіпроменя. Візьмемо першу вершину v: n}, через яку не пройшов відрізок {y0,y1,…, yk}. Нехай z1, z2,…, zm — найкоротший шлях від yk до v, yk =z1, v=zm. Оскільки z2, z3,…, zm-1 — вершини локальної нескінченності, то можна вибрати вершини.

yk+1z2,1) {z1, z2, z3}, yk+2z3,1) {z2, z3, z4},…,.

yk+m-2zm-1,1) {zm-2, zm-1, zm},.

жодна з яких не належить відрізку {y0,y1,…, yk}. Продовжимо відрізок {y0,y1,…, yk} приєднанням до його кінця відрізку {yk+1,yk+2,…, yk+m-2, v}.

Нехай Gr (V, E) — зліченний звязний граф. Бієкцію f: V назвемо квазігамільтоновим променем (скорочено qh-променем), якщо d (f (i), f (i+1))для всіх i. Граф, що допускає таку бієкцію назвемо qhr-графом.

Проблема 6. Охарактеризувати qhr-дерева.

Наступна задача показує, що клас qhr-дерев значно вужчий за клас qr-дерев.

Задача 3. Нехай T (V, E) — зліченне дерево, x/p>

$$T_{y_1}$$, $$T_{y_2}$$, …, $$T_{y_k}$$), |V ($$T_{y_1}$$)|>1, |V ($$T_{y_2}$$)|>1,…|V ($$T_{y_k}$$)|>1.

Якщо T (V, E) — qhr-граф, то kі серед дерев $$T_{y_1}$$, $$T_{y_2}$$, …, $$T_{y_k}$$ не більше одного нескінченного дерева.

Розглянемо деякі алгоритмічні задачі і проблеми, пов’язані з результатами останніх двох параграфів.

Задача 4. Спираючись на доведення теореми 4.1, вказати алгоритм побудови повного квазіциклу в довільному скінченному звязному графі. Оцінити його складність.

Задача 5. Вказати алгоритми, які по заданому скінченному дереву визначають, чи є це дерево qhc-графом, qhp-графом? Оцінити їх складності.

Відомо, що задача перевірки, чи є заданий скінченний звязний граф гамільтоновим, являється NP-повною [6].

Проблема 7. Чи є NP-повною задача тестування скінченного звязного графа на існування в ньому qh-циклу? qh-шляху?