4625
правок
Четный граф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Четный граф''' (''Even graph'') - 1) для разбиения множества вершин <math>V(G)</math> на три...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Четный граф''' (''Even graph'') - | '''Четный граф''' (''[[Even graph]]'') - | ||
1) для разбиения множества вершин <math>V(G)</math> на три множества <math>S, \, T</math> и | 1) для разбиения множества [[вершина|вершин]] <math>V(G)</math> на три множества <math>S, \, T</math> и | ||
<math>U</math> (так называемая <math>G</math>-тройка <math>(S,T,U)</math>), целочисленной функции <math>f: | <math>U</math> (так называемая <math>G</math>-тройка <math>(S,T,U)</math>), целочисленной функции <math>f: | ||
\, V(G) \rightarrow Z</math> и компоненты связности <math>C</math> индуцированного | \, V(G) \rightarrow Z</math> и [[компонента связности|компоненты связности]] <math>C</math> индуцированного [[подграф|подграфа]] <math>G[U]</math> определим ''индекс четности'' | ||
подграфа <math>G[U]</math> определим ''индекс четности'' | |||
<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>\lambda(T,b)</math> - число [[ребро|ребер]], соединяющих вершину <math>b</math> с | ||
вершинами множества <math>T</math>. Граф <math>C</math> называется четным тогда и только | вершинами множества <math>T</math>. [[Граф]] <math>C</math> называется четным тогда и только | ||
тогда, когда <math>I(C)</math> | тогда, когда <math>I(C)</math> - четно; 2) граф с четным числом вершин. | ||
Для функции <math>f</math>, тождественно равной единице, 1) и 2) совпадают. | Для функции <math>f</math>, тождественно равной единице, 1) и 2) совпадают. | ||
==Литература== | ==Литература== | ||
[Татт] | [Татт] | ||