Розкладність графів. Врівноважені розбиття нескінченних графів
Упорядкуємо множину зелених вершин так: першою запишемо вершину , далі випишемо всі вершини першого поверху, слідом за ними всі вершини другого поверху і т. д.
До множини віднесемо корінь і всі вершини, що лежать на шляхах від кореня до жовтих вершин, що проходять через жовті вершини першого поверху. Зокрема, всі жовті вершини першого поверху заносяться до . Якщо у цей список попало вершин, то це і буде множина . Якщо ж ні, то приєднаємо до наступну за зелену вершину і всі жовті вершини, що лежать на шляхах від , що проходять через жовті вершини другого поверху і т. д. Після визначення множини беремо першу за списком зелену вершину, що не увійшла до , і повторюємо для неї цю ж процедуру.
Доведення теореми 4. Скористаємось розбиттям з леми 1 і покладемо . Очевидно, що - покриваюча послідовність. До кожного з графів , застосуємо теорему і зафіксуємо врівноважене -розфарбування індексу . За лемою ці розфарбування можна вибрати так, що є продовженням розфарбування c, . За візьмемо відображення , звуження якого на кожну з підмножин співпадає з . Ясно що розфарбування породжує -розбиття індексу , врівноважене відносно послідовності .
Проблема 1. Нехай Gr(V,E) - довільний зліченний зв'язний граф, - натуральне число. Чи існує - розфарбування індексу множини V, врівноважене відносно деякої покриваючої послідовності скінченних підмножин множини V?
З доведення теореми 4 випливає, що для позитивної відповіді на це питання досить поширити лему 1 на довільні зліченні зв'язні графи. Проте цей шлях безперспективний. Дійсно, розглянемо дерево Gr(V,E) з множиною вершин і множиною ребер . Очевидно, що множина вершин цього дерева не допускає розбиттів, що задовольняють умови леми 1 при .
Проблема 2. Нехай Gr(V,E) - зліченний локально скінченний зв'язний граф, , - довільне натуральне число. Чи існує розбиття індексу множини V на підмножин, врівноважене відносно послідовності ? Ця ж проблема відкрита навіть для дерев.
Розглянемо орієнтовний граф Gr(V,E) з множиною вершин V і множиною орієнтовних ребер E. Вважаємо, що граф не має петель і кратних ребер. Для довільних вершин , підмножини і невід'ємного цілого числа покладемо.
існує орієнтовний шлях довжини від до },
існує орієнтовний шлях довжини від до },
В цих позначеннях враховується, що , для всіх , .
За означенням підмножина має скінченний індекс , (відповідно ), якщо знайдеться таке невід'ємне ціле число , що (відповідно ). Найменші невід'ємні цілі числа, для яких виконуються ці рівності, позначимо через A та відповідно.
Теорема 5. Нехай Gr(V,E) - орієнтовний граф, з кожної вершини якого виходить принаймні одне орієнтовне ребро. Тоді існує розбиття , таке що , .
Доведення. Для кожної вершини виберемо вершину , для якої існує ребро . Таким чином ми визначили відображення . Розглянемо неорієнтовний граф Grf(V,Ef) цього відображення з множиною неорієнтовних ребер . Легко помітити, що кожна зв'язна компонента Grf [S] цього графа може мати не більше одного циклу.Припустимо, що Grf [S] не має жодного циклу. В цьому випадку Grf [S] - нескінченне дерево. Виберемо довільну вершину і назвемо її коренем. Пофарбуємо корінь зеленим кольором. Візьмемо довільну вершину . Якщо відстань від до непарна, пофарбуємо жовтим кольором, а якщо парна - зеленим. Позначимо через і підмножини всіх зелених та жовтих вершин відповідно. Ясно, що .
Нехай в графі Grf [S] є цикл . Якщо число n парне, пофарбуємо вершини циклу по черзі зеленим та жовтим кольорами. Для непарного числа n пофарбуємо вершини x1, x2 зеленим кольором, а вершини x3, x4 ,.., xn по черзі - жовтим та зеленим кольорами. Візьмемо довільну вершину y, що не належить циклу. Виберемо вершину циклу xi, найближчу за відстанню до вершини y. Якщо ця відстань парна, пофарбуємо y кольором вершини xi, якщо непарна, то в інший з двох кольорів. Позначимо через S1 та S2 множини зелених та жовтих вершин. Якщо число n парне, то S1= S2=1. Якщо число n непарне, то S1=1, S2=2