4624
правки
Нечетная компонента: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Нечетная компонента''' (''Odd component'') - (1) Компонента связности графа с нечетн...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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) | ||