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

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

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

Розглянемо довільний зв'язний граф Gr(V,E). За означенням, підмножина має скінченний індекс, якщо знайдеться таке невід'ємне ціле число , що , де для деякої вершини . Найменше невід'ємне ціле число , для якого справедлива ця рівність, називається індексом підмножини і позначається .

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

Почнемо з поширення на нескінченні графи.

Теорема 1. Нехай Gr(V,E) - нескінченний зв'язний граф, - довільне натуральне число. Тоді існує розбиття множини вершин V на підмножин, індекс якого не перевищує .

Доведення. Як і в доведенні теореми граф Gr(V,E) можна вважати деревом. Позначимо через A сім'ю усіх підмножин , таких що , граф зв'язний і існує розфарбування , що задовольняє умову

(*)

для всіх , , де - куля в графі радіуса з центром в вершині . Позначимо через множину усіх пар , для яких A, а розфарбування задовольняє умову (*). Введемо на множині частковий порядок за таким правилом: тоді і тільки тоді, коли і розфарбування є продовженням розфарбування . Зауважимо, що множина непорожня за теоремою. Очевидно, що кожен ланцюг в множині має верхню грань. За лемою Цорна, в множині існує максимальний елемент . Припустимо, що і виберемо вершину , суміжну з деякою вершиною . Оскільки , то для всіх . Виберемо максимальне число , для якого . Далі виберемо довільне число , таке що . Покладемо і для всіх . За побудовою, що суперечить максимальності . Отже, і - шукане розфарбування множини .

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

Приклад 1. Розглянемо довільний метричний простір і припустимо, що для фіксованого додатного числа кожна куля містить деяку точку, відмінну від точки . Покажемо, що існує 2-розфарбування простору , для якого кожна куля радіуса містить різнокольорові точки. Для цього визначимо граф з множиною вершин і множиною ребер . Очевидно, що кожна зв'язна компонента цього графу містить принаймні дві точки. Якщо скінченна, застосуємо для її розфарбування теорему, якщо ж нескінченна - теорему 1.

Теорема 2. Для кожного нескінченного зв'язного графа Gr(V,E) існує розфарбування , таке що для всіх .

Доведення. Спочатку припустимо, що кожна куля , скінченна. Тоді множина зліченна і можна взяти довільну бієкцію .

Припустимо, що деяка вершина є центром нескінченної кулі . Для кожного позначимо . Покладемо , . Покладемо і продовжимо на так, щоб . Далі, для кожної вершини покладемо . Таким чином визначене деяке розфарбування .

Візьмемо довільну вершину . Якщо , то , а множина нескінченна. Якщо , то

,

а множина нескінченна.

Зв'язний граф називається однорідним степеня , якщо локальний степінь кожної його вершини дорівнює . При цьому може бути як скінченним, так і нескінченним кардинальним числом.