Berge's Formula

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

Let [math]\displaystyle{ \,G }[/math] be a graph and let [math]\displaystyle{ \,o(G) }[/math] be the number of odd components of [math]\displaystyle{ \,G }[/math].

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

[math]\displaystyle{ def(G) = \max_{S \subset V(G)} \{o(G \setminus S) - |S|\}. }[/math]

Литература

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