Теорема - менгер
Cтраница 2
Хотя это утверждение типа теоремы Менгера, доказать его значительно проще, чем теорему Менгера. [16]
В этой монографии освещается много центральных тем, которые можно рассчитывать найти в книге по теории графов - например, теорема Менгера и потоки в сетях, проблема восстановления, матричная теорема о деревьях, теория факторов ( или паросочетаний) для графов ( созданная в значительной степени самим профессором Таттом), хроматические многочлены, теорема Брукса, теорема Гринберга, пленарные графы, теорема Куратовского. Но это ни в коем случае не еще одна книга по теории графов, ибо излагаемый материал связывается в единое целое глубоко индивидуальным подходом профессора Татта. Кроме того, самые обычные темы преподносятся с некоторыми приятными сюрпризами, такими, как принадлежащая автору изящная теория разложения графов на трехсвязные 3-блоки ( кроме монографии [5], ее ни в какой книге не найдешь), интересный, замечательный подход к электрическим цепям и - быть может, самое примечательное - классификационная теорема для замкнутых поверхностей. Обычно эту теорему относят к топологии, но проф. Татт демонстрирует нам, что она отлично подходит для работы по теории графов - комбинаторная по своей сущности природа рассуждений здесь, действительно, на месте. [17]
Таким образом, сформулировав результат Уитни в реберной форме, мы, не затрачивая дополнительных усилий, получаем другой вариант теоремы Менгера. [18]
Вообще все приведенные здесь теоремы имеют соответствующие ориентированные формулировки, и, действительно, Дирак указывает, что его доказательство теоремы Менгера пригодно для ориентированных графов. Можно было бы добавить в табл. 5.1 еще 11 теорем, а именно теоремы с номерами от 5.12 до 5.15 и ориентированные варианты теорем от 5.9 до 5.15. Однако это было бы бесполезным занятием, поскольку совершенно ясно, что таблица все равно осталась бы далеко не полной. [19]
Такал редукция дает прекрасные результаты при доказательстве теорем; например, теорему о максимальном потоке и минимальном разрезе можно вывести этим способом из теоремы Менгера. Однако алгоритмически редукция осуществляется за полиномиальное время только при унарном кодировании пропускных способностей. [20]
На первый взгляд кажется удивительным, что не только решение этой задачи имеет вид, подобный теореме 28А, но и само доказательство теоремы 28А претерпевает лишь незначительные изменения, состоящие главным образом в замене таких терминов, как реберно непересекающийся и инцидентный, на термины вершинно непересекающийся и смежный. Сформулируем теперь вершинную форму теоремы Менгера, а доказательство предоставим читателю. [21]
Я не могу припомнить ни одного случая, когда бы я в своих исследованиях использовал ее, исключая чрезвычайно простые и не представляющие существенного интереса ситуации. Понятия, входящие в теорему Менгера и ее аналоги, весьма важны в теории транспортных сетей. [22]
Наряду с различными типами разрезов упаковки различных соединений образуют интересный, но во многих отношениях более сложный круг задач. Задача об упаковке для Т - соединений при Т 2 связана как раз с теоремой Менгера, которая гласит, что максимальное число реберно непересекающихся Т - соединений равно минимальному размеру Г - разреза. [23]
 |
Двудольный граф, иллюстрирующий теорему Холла. [24] |
Обозначим эти вершины через и и v и соединим и с каждой вершиной, соответствующей множеству Sit a v - со всеми вершинами, соответствующими элементам а. Тогда теорему 5.19 можно доказать, применив к полученному графу или теорему о максимальном потоке, или соответствующий реберный вариант теоремы Менгера. [25]
Эти цепи называются внутренне непересекающимися, если ни одно ребро и ни одна внутренняя вершина какой-либо из них не принадлежат другой цепи рассматриваемого множества. Заметим, что две или более внутренне непересекающиеся цепи могут иметь одни и те же пары концов. Обычный вариант теоремы Менгера звучит так. [26]
Только в 1956 г. ( II) был получен соответствующий результат ( Фордом и Фалкерсоном) для не имеющих общих ребер путей, соединяющих пары вершин, и ребер, которые разделяют их. Другая теорема, эквивалентная теореме Менгера, была сформулирована в 1932 г.: ( III) Граф является га-связным тогда и только тогда, когда каждая пара вершин соединяется не менее чем п путями, отличающимися вершинами. Теоремы ( I), ( II) и ( III) являются следствиями теоремы Форда и Фалкерсона о максимальном потоке и минимальном разрезе. Харари указывает, что несколько других теорем, которые на первый взгляд отличаются от теоремы Менгера, на самом деле эквивалентны ей. [27]
Результаты этой главы носят более комбинаторный характер, чем результаты всех предыдущих глав, хотя, как мы увидим, они тесно связаны с теорией графов. Сначала мы обсудим хорошо известную теорему о свадьбах, принадлежащую Филипу Холлу, и некоторые приложения этой теоремы к таким вопросам, как построение латинских квадратов и составление расписаний. Затем в § 28 будет изложена теорема Менгера о числе попарно непересекающихся простых цепей графа, связывающих данную пару вершин. [28]
Следовательно, эти две теоремы в некотором смысле эквивалентны. Позднее в этой главе мы докажем теорему Менгера и теорему о максимальном потоке и минимальном разрезе, каждая из которых тоже эквивалентна теореме Холла. [29]
Легко видеть, что величина любого потока не превышает пропускной способности любого разреза, и, следовательно, величина любого максимального потока не превышает пропускной способности любого минимального разреза. Однако сразу не ясно, что два последних числа всегда равны между собой; этот замечательный результат называется теоремой о максимальном потоке и минимальном разрезе. Впервые она была доказана Фордом и Фалкерсоном в 1955 г. Мы дадим здесь два доказательства; первое из них показывает, что эта теорема по существу эквивалентна теореме Менгера, а второе является прямым доказательством. [30]
Страницы: 1 2 3