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