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

Нечетная компонента (Odd component) — (1) Компонента связности графа с нечетным числом вершин. (2) Пусть множество вершин графа [math]\displaystyle{ \,G }[/math] разбивается на подмножества [math]\displaystyle{ \,S }[/math], [math]\displaystyle{ \,T }[/math] и [math]\displaystyle{ \,U }[/math]. Рассмотрим компоненту [math]\displaystyle{ \,C }[/math] подграфа [math]\displaystyle{ \,G[U] }[/math], индуцированного множеством [math]\displaystyle{ \,U }[/math]. Пусть [math]\displaystyle{ \,f }[/math] — функция из множества [math]\displaystyle{ \,V(G) }[/math] вершин графа в множество неотрицательных целых чисел. Компоненту [math]\displaystyle{ \,C }[/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{ T = \emptyset }[/math] и частного случая [math]\displaystyle{ f \equiv 1 }[/math] на всех вершинах понятия нечетной компоненты (1) и (2) совпадают.

Литература

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

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