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

Материал из WikiGrapp
Перейти к:навигация, поиск
 
Строка 1: Строка 1:
'''Четный граф''' (''[[Even graph]]'') -
+
'''Четный граф''' (''[[Even graph]]'')
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>
+
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>\lambda(T,b)</math> - число [[ребро|ребер]], соединяющих вершину <math>b</math> с
+
:::::<math>I(C) = \sum_{b \in V(C)} \{f(b) + \lambda(T,b)\},</math>
вершинами множества <math>T</math>. [[Граф]] <math>C</math> называется четным тогда и только
 
тогда, когда <math>I(C)</math> - четно; 2) граф с четным числом вершин.
 
  
Для функции <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) для разбиения множества вершин \,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) совпадают.

Литература

  • Татт У. Теория графов. — М.:Мир, 1988.