Нечетная компонента: различия между версиями
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) | ||
Версия от 19:26, 25 ноября 2009
Нечетная компонента (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) совпадают.
Литература
[Харари],
[Татт]