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

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

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

.

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

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

.

, що задовольняє умову

(()

.

парне.

нескінченна - теорему 1.

.

.

.

, то

,

нескінченна.

може бути як скінченним, так і нескінченним кардинальним числом.

кольорів.

кольорів.

можна застосувати стандартний діагональний процес.

кольорів? Наступний приклад дає негативну відповідь на це питання. Більше того, він показує, що навіть 3-розфарбування з цією властивістю може не існувати.

.

кольорів.

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

назвемо покриваючою, якщо виконуються такі умови:

;

;

зв'язний.

, якщо