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

Материал из WikiGrapp
Перейти к:навигация, поиск
(Создана новая страница размером '''Четный граф''' (''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) для разбиения множества вершин V(G) на три множества S, \, T и U (так называемая G-тройка (S,T,U)), целочисленной функции f:
\, V(G) \rightarrow Z и компоненты связности C индуцированного подграфа G[U] определим индекс четности

I(C) = \sum_{b \in V(C)} \{f(b) + \lambda(T,b)\},

где \lambda(T,b) - число ребер, соединяющих вершину b с вершинами множества T. Граф C называется четным тогда и только тогда, когда I(C) - четно; 2) граф с четным числом вершин.

Для функции f, тождественно равной единице, 1) и 2) совпадают.

Литература

[Татт]