Четный граф

Материал из WikiGrapp
Версия от 15:59, 16 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Четный граф''' (''Even graph'') - 1) для разбиения множества вершин <math>V(G)</math> на три...)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Четный граф (Even graph) - 1) для разбиения множества вершин V(G) на три множества S, \, T и U (так называемая G-тройка (S,T,U)), целочисленной функции f:
\, V(G) \rightarrow Z и компоненты связности C индуцированного подграфа G[U] определим индекс четности

I(C) = \sum_{b \in V(C)} \{f(b) + \lambda(T,b)\},

где \lambda(T,b) --- число ребер, соединяющих вершину b с вершинами множества T. Граф C называется четным тогда и только тогда, когда I(C) --- четно; 2) граф с четным числом вершин.

Для функции f, тождественно равной единице, 1) и 2) совпадают.

Литература

[Татт]