Теорема Менгерса - Mengers theorem - Wikipedia

в математический дисциплина теория графов, Теорема Менгера говорит, что в конечный граф, размер минимум вырезать набор равно максимальному количеству непересекающихся путей, которые могут быть найдены между любой парой вершин. Карл Менгер в 1927 г. характеризует то возможность подключения графа и обобщается теорема о максимальном потоке и минимальном отсечении, который является взвешенной версией с ребром и, в свою очередь, является частным случаем сильная теорема двойственности для линейных программ.

Пограничное соединение

В граничное соединение версия теоремы Менгера выглядит следующим образом:

Позволять грамм конечный неориентированный граф и Икс и у две разные вершины. Тогда размер минимальный обрезка края за Икс и у (минимальное количество ребер, удаление которых отключает Икс и у) равно максимальному количеству попарных пути, независимые от краев из Икс к у.
Распространяется на все пары: график k-ребневой (он остается подключенным после удаления менее чем k ребер) тогда и только тогда, когда каждая пара вершин имеет k рёберно непересекающиеся пути между ними.

Связность вершин

В вершинная связность Формулировка теоремы Менгера выглядит следующим образом:

Позволять грамм конечный неориентированный граф и Икс и у два несмежный вершины. Тогда размер минимальный вершинный разрез за Икс и у (минимальное количество вершин, отличное от Икс и у, удаление которых отключает Икс и у) равно максимальному количеству попарных внутренне вершинно-непересекающиеся пути из Икс к у.
Распространен на все пары: график k-вершинно-связанный (более чем k вершин, и он остается связанным после удаления менее чем k вершин) тогда и только тогда, когда каждая пара вершин имеет не менее k внутри вершинно-непересекающиеся пути между ними.

Все эти утверждения (как для ребер, так и для вершин) остаются верными в ориентированных графах (при рассмотрении ориентированных путей).

Краткое доказательство

В большинстве прямых доказательств рассматривается более общее утверждение, позволяющее доказать его по индукции. Также удобно использовать определения, которые включают некоторые вырожденные случаи. Следующее доказательство для неориентированных графов работает без изменений для ориентированных графов или мульти-графов, если мы берем дорожка означать направленный путь.

Для наборов вершин A, B ⊂ G (не обязательно непересекающиеся), AB-путь это путь в грамм с начальной вершиной в А, последняя вершина в B, и никаких внутренних вершин в А или же B. Мы допускаем путь с единственной вершиной в А ∩ Б и нулевые ребра. АБ-сепаратор размера k это набор S из k вершины (которые могут пересекаться А и B) такие, что G − S не содержит AB-path.An AB-коннектор размера k это союз k вершинно-непересекающийся AB-путь.

Теорема: Минимальный размер AB-сепаратор равен максимальному размеру AB-разъем.

Другими словами, если нет k−1 вершина разъединяется А из B, то существуют k непересекающиеся пути из А к BЭтот вариант подразумевает указанное выше утверждение связности вершин: для x, y ∈ G в предыдущем разделе примените текущую теорему к грамм−{х, у} с А = N (х), B = N (у), соседние вершины х, у. Тогда набор вершин, разъединяющих Икс и у это то же самое, что иAB-сепаратор и удаление конечных вершин в наборе независимых ху-paths дает AB-разъем.

Доказательство теоремы:[1]Индукция по количеству ребер в грамм.За грамм без краев, минимум AB-сепаратор А ∩ Б, который сам по себе AB-коннектор, состоящий из одновершинных путей.

За грамм имея преимущество е, по индукции можно считать, что теорема верна для G − e. Если G − e имеет минимальный AB-сепаратор размера k, то есть AB-разъем размера k в G − e, а значит, в грамм.

Иллюстрация к доказательству.

В противном случае пусть S быть AB-сепаратор G − e размером менее k, так что каждый AB-путь в грамм содержит вершину S или край е.Размер S должно быть к-1, поскольку если бы было меньше, S вместе с любой конечной точкой е было бы лучше AB-сепаратор грамм.В G − S существует AB-путь через е, поскольку S сам по себе слишком мал, чтобы быть AB-сепаратор грамм.Позволять v1 быть раньше и v2 быть более поздней вершиной е на таком пути. v1 доступен из А но не из B в G − S − e, пока v2 доступен из B но не из А.

Теперь позвольте S1 = S ∪ {v1}, и рассмотрим минимум В КАЧЕСТВЕ1-разделитель Т в G − e.С v2 недоступен из А в G − S1, Т также является В КАЧЕСТВЕ1-сепаратор в грамм.Потом Т также является AB-сепаратор в грамм (потому что каждый AB-путь пересекает S1Значит, он имеет размер не менее k.По индукции G − e содержит В КАЧЕСТВЕ1-разъем C1 размера k. Из-за его размера конечные точки путей в нем должны быть точно S1.

Аналогично, позволяя S2 = S ∪ {v2}, минимум S2B-сепаратор имеет размер k, и есть S2B-разъем C2 размера k, с путями, начальные точки которых точно S2.

Кроме того, поскольку S1 отключает грамм, каждый путь в C1 внутренне не пересекается с каждым путем в C2, и мы можем определить AB-разъем размера k в грамм путем объединения путей (к − 1 пути через S и один путь проходит е = v1v2). Q.E.D.

Прочие доказательства

Из версии теоремы с ориентированным ребром легко вытекают и другие версии. Чтобы получить версию с вершинами ориентированного графа, достаточно разбить каждую вершину v на две вершины v1, v2, со всеми входящими кромками v1, все исходящие ребра, идущие из v2, и дополнительное ребро из v1 к v2Из направленных версий теоремы сразу следует неориентированные версии: достаточно заменить каждое ребро неориентированного графа парой ориентированных ребер (двуугольником).

Версия с направленным краем, в свою очередь, следует из ее взвешенного варианта: теорема о максимальном потоке и минимальном отсечении.Его доказательства часто служат доказательством корректности алгоритмов максимального потока. Это также частный случай еще более общего (сильного) теорема двойственности за линейные программы.

Формулировка, которая для конечных орграфов эквивалентна приведенной выше формулировке:

Позволять А и B - множества вершин в конечном диграф грамм. Тогда существует семья п непересекающихся AB-путь и AB-разделяющее множество, состоящее ровно из одной вершины каждого пути в п.

В этой версии теорема довольно легко следует из Теорема Кенига: в двудольном графе минимальный размер покрытия равен максимальному размеру сопоставления.

Это делается следующим образом: заменить каждую вершину v в исходном орграфе D на две вершины v ' , v '', и каждый край УФ по краю u'v ''. В результате получается двудольный граф, одна сторона которого состоит из вершин v ' , а другая из вершин v ''.

Применяя теорему Кенига, получаем паросочетание M и крышка C такого же размера. В частности, ровно по одному концу каждого ребра M в C. Добавить к C все вершины а '', за а в А, и все вершины б ' , за б в B. Позволять п быть набором всех AB-путь, состоящий из ребер УФ в D такой, что u'v '' принадлежит М. Пусть Q в исходном графе состоят из всех вершин v так что оба v ' и v '' принадлежать C. Несложно проверить, что Q является AB-разделительный набор, что каждый путь в семье п содержит ровно одну вершину из Q, и каждая вершина в Q лежит на пути от п, по желанию.[2]

Бесконечные графы

Теорема Менгера верна для бесконечных графов, и в этом контексте она применяется к минимальному разрезу между любыми двумя элементами, которые являются либо вершинами, либо заканчивается графа (Халин 1974 ). Следующий результат Рон Ахарони и Эли Бергер первоначально была гипотеза, предложенная Пол Эрдёш, и до того, как был доказан, был известен как Гипотеза Эрдеша – МенгераЭто эквивалентно теореме Менгера, когда граф конечен.

Позволять А и B - множества вершин в (возможно, бесконечном) диграф грамм. Тогда существует семья п непересекающихся А-B-путь и разделяющий набор, который состоит ровно из одной вершины из каждого пути в п.

Смотрите также

Рекомендации

  1. ^ Ф. Геринг, Краткое доказательство теоремы Менгера, Дискретная математика 219 (2000) 295-296.)
  2. ^ Ахарони, Рон (1983). «Теорема Менгера для графов, не содержащих бесконечных путей». Европейский журнал комбинаторики. 4 (3): 201–4. Дои:10.1016 / S0195-6698 (83) 80012-2.

дальнейшее чтение

  • Менгер, Карл (1927). "Zur allgemeinen Kurventheorie". Фонд. Математика. 10: 96–115.
  • Ахарони, Рон; Бергер, Эли (2008). «Теорема Менгера для бесконечных графов». Математические изобретения. 176: 1. arXiv:математика / 0509397. Bibcode:2009ИнМат.176 .... 1А. Дои:10.1007 / s00222-008-0157-3.
  • Халин, Р. (1974). «Заметка к теореме Менгера для бесконечных локально конечных графов». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 40: 111. Дои:10.1007 / BF02993589.

внешняя ссылка