Нечетная компонента: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Нечетная компонента''' (''[[Odd component]]'') -
'''Нечетная компонента''' (''[[Odd component]]'')
(1) [[Компонента связности]] [[граф|графа]] с нечетным числом [[вершина|вершин]]. (2) Пусть
(1) [[Компонента связности]] [[граф|графа]] с нечетным числом [[вершина|вершин]]. (2) Пусть
множество вершин графа <math>G</math> разбивается на подмножества <math>S</math>, <math>T</math> и <math>U</math>.
множество вершин графа <math>\,G</math> разбивается на подмножества <math>\,S</math>, <math>\,T</math> и <math>\,U</math>.
Рассмотрим компоненту <math>C</math> [[подграф|подграфа]] <math>G[U]</math>, индуцированного множеством
Рассмотрим компоненту <math>\,C</math> [[подграф|подграфа]] <math>\,G[U]</math>, индуцированного множеством
<math>U</math>. Пусть <math>f</math> --- функция из множества <math>V(G)</math> вершин графа в
<math>\,U</math>. Пусть <math>\,f</math> функция из множества <math>\,V(G)</math> вершин графа в
множество неотрицательных целых чисел. Компоненту <math>C</math> будем называть
множество неотрицательных целых чисел. Компоненту <math>\,C</math> будем называть
нечетной (или четной) в соответствии с нечетностью (четностью) индекса
нечетной (или четной) в соответствии с нечетностью (четностью) индекса
четности
четности
Строка 10: Строка 10:
<math>I(C) = \sum_{b  \in V(C)}  \{f(b) + \lambda(T,b)\},</math>
<math>I(C) = \sum_{b  \in V(C)}  \{f(b) + \lambda(T,b)\},</math>


где <math>\lambda(T,b)</math> есть число [[ребро|ребер]], соединяющих вершину <math>b</math> с
где <math>\,\lambda(T,b)</math> есть число [[ребро|ребер]], соединяющих вершину <math>\,b</math> с
вершинами множества <math>T</math>. Для <math>T = \emptyset</math> и частного случая <math>f
вершинами множества <math>\,T</math>. Для <math>T = \emptyset</math> и частного случая <math>f
\equiv 1</math> на всех вершинах понятия нечетной компоненты (1) и (2)
\equiv 1</math> на всех вершинах понятия нечетной компоненты (1) и (2)
совпадают.
совпадают.
==Литература==
==Литература==
[Харари],  
* Татт У. Теория графов. — М.:Мир, 1988.


[Татт]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Навигация