Теорема Менгера: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Теорема Менгера''' (''K.Menger, 1927'') -  
'''Теорема Менгера''' (''[[K.Menger, 1927]]'') -  
''Наименьшее число [[вершина|вершин]], разделяющих две [[смежные вершины|несмежные вершины]] <math>a</math> и <math>b</math> [[граф|графа]], равно наибольшему числу попарно непересекающихся [[простая цепь|простых <math>(a,b)</math>-цепей]] этого графа.''
''Наименьшее число [[вершина|вершин]], разделяющих две [[смежные вершины|несмежные вершины]] <math>a</math> и <math>b</math> [[граф|графа]], равно наибольшему числу попарно непересекающихся [[простая цепь|простых <math>(a,b)</math>-цепей]] этого графа.''



Версия от 13:04, 4 февраля 2010

Теорема Менгера (K.Menger, 1927) - Наименьшее число вершин, разделяющих две несмежные вершины [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] графа, равно наибольшему числу попарно непересекающихся простых [math]\displaystyle{ (a,b) }[/math]-цепей этого графа.

Теорема Менгера известна в литературе в нескольких вариантах.

Литература

[Харари],

[Лекции]