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

Материал из WikiGrapp
Перейти к:навигация, поиск

Нечетная компонента (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.