Нечетный цикл

Cтраница 3

Второе обстоятельство, заставившее нас предпринять эту работу, примечание в работе Куртина и Крумпа [12], где они подвергают сомнению применимость нашего метода установления сохранения конфигурации четных и нечетных циклов. [31]

Тогда G является - раскрашиваемым, за исключением тех случаев, когда граф G содержит в качестве компоненты полный р 1-вер-шинник или когда р 2 и одна из компонент графа G является нечетным циклом. [32]

Если все веса равны - 1, то задача нахождения разреза с минимальным весом эквивалентна задаче нахождения максимального разреза или, что то же самое, задаче нахождения минимального числа ребер, удаление которых разрушает все нечетные циклы. Действительно, в случае планарных графов задачу о разрезе с минимальным весом можно решить при любых ( отрицательных или положительных) весах. [33]

Исключительные подгрг1фы, связанные со свойством Кенига. [34]

Сначала предположим, что граф G имеет совершенное 2-паросо-четание, которое содержит нечетный цикл. Пусть и является таким 2-паросочетанием с наименьшим числом нечетных циклов. [35]

Любой вектор у, удовлетворяющий ограничениям этой двойственной программы, будем коротко называть двойственным решением. Такое двойственное решение мы можем рассматривать как упаковку нечетных циклов, где каждое ребро е имеет мощность w ( e) и каждый нечетный разрез С встречается ус раз. Заметим, однако, что величина ус может быть дробной и мы даже можем получить ус 0 для тривиальных нечетных разрезов. [36]

Доказать, что если G - простой граф с максимальной степенью k и каждый цикл в нем проходит через вершину степени не выше k - 1, то граф G реберно - раскрашиваемый. Мы думаем, что в этом упражнении достаточно ограничиться нечетными циклами. [37]

Основная трудность алгоритма Эдмондса связана с процедурой сжатия циклов. Совсем не просто построить граф, получаемый в результате сжатия подходящего нечетного цикла. Мы должны затем восстановить исходный граф, чтобы построить увеличенное паросочетание исходного графа из увеличенного паросочетания сжатого графа. Повторяемое сжатие нечетных циклов будет отображать факторно-критические графы в вершины; такие факторно-критические графы мы называем цветками. Когда мы делаем шаг увеличения, мы должны располагать достаточной информацией о структуре цветков, чтобы иметь возможность в каждом из них легко найти почти совершенное паросочетание, пропускающее любую заданную вершину. [38]

Среднее количество операций может быть уменьшено, если использовать способ деления без восстановления остатков. Этот способ отличается от предыдущего тем, что при выполнении первого и всех последующих нечетных циклов деления ( нулевой цикл считается четным) восстановления остатков не производится. Цифра частного в каждом из нечетных циклов определяется так же, как и в случае деления с восстановлением остатков, по количеству полученных переносов. После этого делитель сдвигается вправо на один разряд и начинается выполнение следующего ( четного) цикла. [39]

Базисное и небазисное 2-паросочетания. [40]

Ребра веса 1 образуют вершинно непересекающиеся простые цепи и циклы. Мы говорим, что 2-паросочетание является базисным, если его ребра веса 1 образуют только нечетные циклы. Очевидно, что такие нечетные циклы не должны иметь общих вершин. [41]

Критически несовершенным графом называется несовершенный граф, все порожденные подграфы которого совершенны. Показать, что сильная гипотеза Бержа эквивалентна следующей: каждый критически несовершенный граф является либо нечетным циклом без хорд длины, не меньшей 5, либо его дополнением. [42]

Теперь мы приходим к другому очень полезному результату о структуре r - критических графов. Андрашфаи ( 1967) доказал, что любые два смежных ребра r - критического графа содержатся в нечетном цикле, а Байнеке, Харари и Пламмер ( 1967) установили, что любые два смежных ребра т-критического графа содержатся в цикле без хорд. Следующая теорема Бержа ( 1972) дает естественное обобщение этих двух результатов. [43]

Достаточно проверить истинность второго высказывания, так как из него очевидным образом следует первое. Но если х - и ху не находятся на расстоянии 2 при обходе цикла, то мы можем найти нечетный цикл в G [ N ( a) ], который короче, чем цикл С, что противоречит выбору С. [44]

Циклом без хорд графа G называется цикл, каждая вершина которого в графе G инцидентна точно двум вершинам цикла. Гипотеза Бержа: граф G является совершенным тогда и только тогда, когда ни он, ни его дополнение не содержат нечетных циклов длины, не меньшей 5 без хорд. [45]

Страницы: 1 2 3 4