Четный граф

Материал из 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) совпадают.

Литература

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