Четный граф

Четный граф (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)$ — четно;