Четный граф

Четный граф (Even graph) —

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

[math]\displaystyle{ I(C) = \sum_{b \in V(C)} \{f(b) + \lambda(T,b)\}, }[/math]

где [math]\displaystyle{ \,\lambda(T,b) }[/math] — число ребер, соединяющих вершину [math]\displaystyle{ \,b }[/math] с вершинами множества [math]\displaystyle{ \,T. }[/math] Граф [math]\displaystyle{ \,C }[/math] называется четным тогда и только тогда, когда [math]\displaystyle{ \,I(C) }[/math] — четно;

2) граф с четным числом вершин.

Для функции [math]\displaystyle{ \,f }[/math], тождественно равной единице, 1) и 2) совпадают.

Литература

• Татт У. Теория графов. — М.:Мир, 1988.