Berge's Formula

Материал из WikiGrapp
Перейти к:навигация, поиск

Berge's Formulaформула Бержа.

Let \,G be a graph and let \,o(G) be the number of odd components of \,G.

Berge's Formula for estimating the deficiency of the graph:

def(G) = \max_{S \subset V(G)} \{o(G \setminus S) - |S|\}.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.