Нечетная компонента

Нечетная компонента (Odd component) — (1) Компонента связности графа с нечетным числом вершин. (2) Пусть множество вершин графа $\,G$ разбивается на подмножества $\,S$, $\,T$ и $\,U$. Рассмотрим компоненту $\,C$ подграфа $\,G[U]$, индуцированного множеством $\,U$. Пусть $\,f$ — функция из множества $\,V(G)$ вершин графа в множество неотрицательных целых чисел. Компоненту $\,C$ будем называть нечетной (или четной) в соответствии с нечетностью (четностью) индекса четности

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

где $\,\lambda(T,b)$ есть число ребер, соединяющих вершину $\,b$ с вершинами множества $\,T$. Для $T = \emptyset$ и частного случая $f \equiv 1$ на всех вершинах понятия нечетной компоненты (1) и (2) совпадают.

Литература

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

• Харари Ф. Теория графов. — М.: Мир, 1973.