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

є покриваючою послідовністю, а тому покриваючою буде і будь-яка її підпослідовність.

.

Для доведення теореми скористаємося такою лемою.



;

зв'язний;

зв'язний.

теж фарбується зеленим кольором. Решта вершин дерева фарбується жовтим кольором. Ясно, що множина зелених вершин нескінченна, проте не виключено, що множина жовтих вершин виявилася порожньою.

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

, і повторюємо для неї цю ж процедуру.

.

множини V, врівноважене відносно деякої покриваючої послідовності скінченних підмножин множини V?

.

? Ця ж проблема відкрита навіть для дерев.

покладемо.

},

},



.

відповідно.

.

. Легко помітити, що кожна зв'язна компонента Grf [S] цього графа може мати не більше одного циклу.

.

S2=2

Задача 3. Нехай S - напівгрупа, a(S і ax(x для всіх x(S. Довести, що існує розбиття S=A1(A2, таке що

S=A1( a-1A1, S=A2( a-1A2( a-2A2,

де a-1Ai ={x(S : ax(Ai}, a-2Ai={x(S : a2x(Ai}.

V2( 2.

Доведення. Скористаємося схемою і позначеннями з доведення попередньої теореми. Якщо граф Grf [S] має кінцеві вершини, пофарбуємо їх зеленим кольором.