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

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

ГоловнаМатематика, Геометрія, Статистика → Розкладність графів. Врівноважені розбиття нескінченних графів - Реферат

Розкладність графів. Врівноважені розбиття нескінченних графів - Реферат


Реферат на тему:
Розкладність графів. Врівноважені розбиття нескінченних графів
Розглянемо довільний зв'язний граф Gr(V,E). За означенням, підмножина має скінченний індекс, якщо знайдеться таке невід'ємне ціле число , що , де для деякої вершини . Найменше невід'ємне ціле число , для якого справедлива ця рівність, називається індексом підмножини і позначається .
За означенням, розбиття множини вершин графа на скінченне число підмножин має скінченний індекс, якщо всі підмножини розбиття є підмножинами скінченного індексу. Найбільший з індексів підмножин розбиття називається індексом розбиття.
Почнемо з поширення на нескінченні графи.
Теорема 1. Нехай Gr(V,E) - нескінченний зв'язний граф, - довільне натуральне число. Тоді існує розбиття множини вершин V на підмножин, індекс якого не перевищує .
Доведення. Як і в доведенні теореми граф Gr(V,E) можна вважати деревом. Позначимо через A сім'ю усіх підмножин , таких що , граф зв'язний і існує розфарбування , що задовольняє умову
( )
для всіх , , де - куля в графі радіуса з центром в вершині . Позначимо через множину усіх пар , для яких A, а розфарбування задовольняє умову ( ). Введемо на множині частковий порядок за таким правилом: тоді і тільки тоді, коли і розфарбування є продовженням розфарбування . Зауважимо, що множина непорожня за теоремою. Очевидно, що кожен ланцюг в множині має верхню грань. За лемою Цорна, в множині існує максимальний елемент . Припустимо, що і виберемо вершину , суміжну з деякою вершиною . Оскільки , то для всіх . Виберемо максимальне число , для якого . Далі виберемо довільне число , таке що . Покладемо і для всіх . За побудовою, що суперечить максимальності . Отже, і - шукане розфарбування множини .
Зауважимо, що для можна вказати значно простіше доведення теореми. Дійсно, зафіксуємо довільну вершину і для кожної вершини покладемо , якщо число непарне, і якщо число парне.
Приклад 1. Розглянемо довільний метричний простір і припустимо, що для фіксованого додатного числа кожна куля містить деяку точку, відмінну від точки . Покажемо, що існує 2-розфарбування простору , для якого кожна куля радіуса містить різнокольорові точки. Для цього визначимо граф з множиною вершин і множиною ребер . Очевидно, що кожна зв'язна компонента цього графу містить принаймні дві точки. Якщо скінченна, застосуємо для її розфарбування теорему, якщо ж нескінченна - теорему 1.
Теорема 2. Для кожного нескінченного зв'язного графа Gr(V,E) існує розфарбування , таке що для всіх .
Доведення. Спочатку припустимо, що кожна куля , скінченна. Тоді множина зліченна і можна взяти довільну бієкцію .
Припустимо, що деяка вершина є центром нескінченної кулі . Для кожного позначимо . Покладемо , . Покладемо і продовжимо на так, щоб . Далі, для кожної вершини покладемо . Таким чином визначене деяке розфарбування .
Візьмемо довільну вершину . Якщо , то , а множина нескінченна. Якщо , то
,
а множина нескінченна.
Зв'язний граф називається однорідним степеня , якщо локальний степінь кожної його вершини дорівнює . При цьому може бути як скінченним, так і нескінченним кардинальним числом.
Задача 1. Нехай - натуральне число, Gr(V,E) однорідне дерево степеня . Довести, що існує розфарбування , таке що кожна куля радіуса 1 містить точки усіх кольорів.
Теорема 3. Нехай - нескінченний кардинал, Gr(V,E) - однорідний граф степеня . Тоді існує таке розфарбування , що кожна куля радіуса 1 містить точки усіх кольорів.
Доведення. З однорідності Gr(V,E) випиває, що . Отже, існує перелік множини і для побудови можна застосувати стандартний діагональний процес.
У зв'язку з теоремою 3 виникає таке питання. Нехай - нескінченний кардинал, Gr(V,E) - зв'язний граф, причому для всіх . Чи можна розфарбувати множину вершин кольорами так, щоб кожна куля радіуса 1 містила точки усіх кольорів? Наступний приклад дає негативну відповідь на це питання. Більше того, він показує, що навіть 3-розфарбування з цією властивістю може не існувати.
Приклад 2. Нехай - нескінченний кардинал, - множина потужності , - сім'я усіх підмножин потужності множини . Розглянемо граф Gr(V,E) з множиною вершин і множиною ребер вигляду , де і . Зафіксуємо довільне 3-розфарбування . Оскільки множина нескінченна, то знайдеться однокольорова підмножина множини . Але тоді куля містить точки щонайбільше двох кольорів. Залишилось зауважити, що для всіх , а для всіх .
Задача 2. Нехай - нескінченний кардинал, Gr(V,E) - дерево і для всіх . Довести, що існує - розфарбування множини , таке що кожна куля радіуса 1 містить точки усіх кольорів.
Для того, щоб ввести поняття врівноваженого розбиття множини вершин нескінченного зв'язного графа дамо таке означення.
Нехай Gr(V,E) - зліченний зв'язний граф. Послідовність скінченних підмножин множини назвемо покриваючою, якщо виконуються такі умови:
(і) ;
(іі) при ;
(ііі) кожен індукований підграф зв'язний.
Розбиття назвемо врівноваженим відносно покриваючої послідовності , якщо
Граф називається локально скінченним, якщо локальний степінь кожної його вершини скінченний. Нехай Gr(V,E) - зліченний локально скінченний граф, . Очевидно, що є покриваючою послідовністю, а тому покриваючою буде і будь-яка її підпослідовність.
Теорема 4. Для кожного зв'язного локально скінченного зліченного графа Gr(V,E) і кожного натурального числа існує розбиття індексу множини на підмножин, врівноважене відносно деякої покриваючої послідовності скінченних підмножин множини .
Для доведення теореми скористаємося такою лемою.
Лема 1. Нехай Gr(V,E) - зліченний зв'язний локально скінченний граф, - довільне натуральне число. Тоді існує розбиття множини вершин на скінченні підмножини , таке що для всіх
(і) ;
(іі) граф зв'язний;
(ііі) граф зв'язний.
Доведення. Не звужуючи загальності, можна вважати, що Gr(V,E) - дерево. Зафіксуємо довільну вершину і назвемо її коренем. Для кожного назвемо -им поверхом дерева множину усіх вершин, відстань від яких до кореня дорівнює . Оскільки дерево Gr(V,E) локально скінченне, то кожен його поверх скінченний. Розфарбуємо множину вершин V двома кольорами, зеленим і жовтим, за таким правилом. Вершина фарбується зеленим кольором тоді і тільки тоді, коли через неї проходить нескінченне число нескінченних шляхів, що виходять з кореня. Корінь теж фарбується зеленим кольором. Решта вершин дерева фарбується жовтим кольором. Ясно, що множина зелених вершин нескінченна, проте не виключено, що множина жовтих вершин виявилася порожньою.
Упорядкуємо множину зелених вершин так: першою запишемо вершину , далі випишемо всі вершини першого поверху, слідом за ними всі вершини другого поверхуі т. д.
До множини віднесемо корінь і всі вершини, що лежать на шляхах від кореня до жовтих вершин, що проходять через жовті вершини першого поверху. Зокрема, всі жовті вершини першого поверху заносяться до . Якщо у цей список попало вершин, то це і буде множина . Якщо ж ні, то приєднаємо до наступну за зелену вершину і всі жовті вершини, що лежать на шляхах від , що проходять через жовті вершини другого поверху і т. д. Після визначення
Loading...

 
 

Цікаве