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

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

Назва:
Розкладність графів. Врівноважені розбиття нескінченних графів
Тип:
Реферат
Мова:
Українська
Розмiр:
95,24 KB
Завантажень:
67
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4 
Реферат на тему:

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

Розглянемо довільний зв'язний граф 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 містить точки усіх кольорів.

Для того, щоб ввести поняття врівноваженого розбиття множини вершин нескінченного зв'язного графа дамо таке означення.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок