Четный граф: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Четный граф''' (''Even graph'') - 1) для разбиения множества вершин <math>V(G)</math> на три...)
 
Нет описания правки
Строка 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>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> --- четно; 2) граф с четным числом вершин.
тогда, когда <math>I(C)</math> - четно; 2) граф с четным числом вершин.


Для функции <math>f</math>, тождественно равной единице, 1) и 2) совпадают.
Для функции <math>f</math>, тождественно равной единице, 1) и 2) совпадают.
==Литература==
==Литература==
[Татт]
[Татт]

Версия от 11:11, 13 мая 2010

Четный граф (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) совпадают.

Литература

[Татт]