Четный граф

Материал из WikiGrapp
Перейти к:навигация, поиск

Четный граф (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) совпадают.

Литература

[Татт]