4194
правки
Нечетная компонента: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
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. | |||