Теорема - татт
Cтраница 1
 |
Четырехчленное соотношение для графов пересечений. [1] |
Теорема Татта гласит, что ответ не зависит от того, в каком порядке стягиваются ребра. [2]
Используя теорему Татта 5.7, показать, что граф, являющийся кубом другого графа, трехсвязен. [3]
В силу теоремы Татта, граф G должен иметь совершенное паросочетание. [4]
Мы применим теорему Татта. Это тривиально, если множество X не разделяет граф; поэтому предположим, что X - разделяющее множество. [5]
Как мы вскоре убедимся, теорема Татта показывает, что если граф не имеет совершенного паросочетания, то в нем должно существовать разрезающее множество вершин определенного типа. [6]
Многие интересные результаты, в том числе и сама теорема Татта, являются следствиями этой структурной теоремы. [7]
Сейчас мы представим результат, следствия из которого в теории паросочетаний так же значительны, как и теорема Татта, но он не является широко известным. [8]
Вновь зададимся вопросом о том, в каком случае граф обладает совершенным паросочетанием. Теорема Татта обеспечивает нас необходимым и достаточным условием существования совершенного паро-сочетания. Однако имеется довольно много интересных результатов, в которых даются достаточные ( но не являющиеся необходимыми) условия. Не удивительно, что большинство соответствующих доказательств начинаются с рассмотрения декомпозиции Татта и с предположения о том, что граф не имеет совершенного паросочетания. Применяя затем рассуждения, базирующиеся на подсчетах и оценках, приходят к противоречию. В рамках этой идеи аргументация обычно весьма проста, хотя иногда скучновата. [9]
Из этого мощного результата следуют почти все ранее известные результаты о паросочетаниях - например, теорема Петерсена ( теорема 3.4.1) и теорема о свадьбах. Сила теоремы Татта в том, что она устанавливает необходимое и достаточное условие существования совершенного паросочетания в общем графе. Мы рассмотрим эту теорему, а также ее несовершенную версию, называемую формулой Бержа, в разд. [10]
Для получения обратного неравенства построить из G новый граф G, добавляя к V ( G ] множество Я, состоящее из 6 ( G) новых вершин, и соединяя все вершины из Я между собой и с каждой вершиной графа G. Затем, применяя теорему Татта, показать, что граф G имеет совершенное паросочетание. [11]
Равенство, содержащееся в этой теореме, часто называют формулой Бержа. В приводимом здесь доказательстве теорема Татта не используется. [12]
Бержа проходит через саму теорему Татта. [13]
Напомним, что граф называется циклически Аг-реберносвяз-ным, если он не может быть разделен посредством удаления менее чем k ребер на две компоненты, каждая из которых содержит цикл. Доказательство следующего результата является непосредственным приложением теоремы Татта. [14]
Полученные результаты справедливы также для мультиграфов и псевдографов. В частности, для псевдографов справедлива теорема 1, так как она опирается на теорему Татта ( лемму 1) для псевдографов. [15]
Страницы: 1 2