Нечетная компонента: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
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>\,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. | |||
Текущая версия от 11:00, 20 мая 2011
Нечетная компонента (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.