Cтраница 1
Нечетный цикл представляет собой очередное движение ртути слева направо. Прямыми линиями изображены поры, заполняемые ртутью именно в рассматриваемом цикле номер 2k 1, волнистыми - остающиеся пустыми после 2k 1 цикла. Двойные прямые линии изображают поры, заполненные ртутью в предыдущих циклах. [1]
Нечетный цикл представляет собой очередное движение ртути слева направо. Прямыми линиями изображены поры, заполняемые ртутью именно в рассматриваемом цикле номер 2k - f - 1, волнистыми - остающиеся пустыми после 2k 1 цикла. Двойные прямые линии изображают поры, заполненные ртутью в предыдущих циклах. [2]
Открытый нечетный цикл также не касается одного из открытых четных циклов. [3]
Обозначим нечетный цикл длины, большей 3, с которого начинается колосковое представление, через С. Цикл С является эластичным подграфом в блоке В и, следовательно, в графе G, Взяв ребра цикла С с весом 1, а ребра совершенного паросочетания в G - V ( C) с весом 2, мы получим 2-паросочетание без ЛГ-угольников. Значит, G не является 3 -угольно-критическим графом. [4]
Тогда каждая вершина нечетного цикла принадлежит четному числу 2-подмножеств, входящих в циклы из U. Каждая вершина четного цикла Zk может содержаться либо в четном, либо в нечетном числе этих 2-подмножеств. [5]
Uu тоже является нечетным циклом наименьшей длины в G [ N ( a) ], и, поскольку v ф Xi ( потому что вершина х - смежна с и), то цикл С1 содержит больше вершин типа и и v, чем цикл С, т.е. мы пришли к противоречию. Итак, мы знаем, что вершина и является смежной со всеми, кроме, быть может, одной, вершинами из С. [6]
Пусть граф G содержит нечетный цикл. [7]
Сд матрицы А не содержит нечетных циклов без хорд. [8]
Очевидно, что граф с нечетным циклом двудольным не является. [9]
Предложение 3.8. Если гиперграф не содержит нечетных циклов, то он - унимодулярный. [10]
Итак, граф Д не содержит нечетных циклов; стало быть, он двудолен. Эквивалентно: всякая вершина в Г лежит в двух больших кликах размера п - 1, а всякое ребро - в единственной большой клике. Имеется ( ( п - 1) п / 2) ( II ( п - 1)) п больших клик и две, имеющие не более ( а значит, точно) чем одну общую вершину. [11]
Но тогда Р вместе с Е образует несбалансированный нечетный цикл. [12]
Всякие два смежных ребра т-критического графа содержатся в нечетном цикле без хорд. [13]
Тогда минимальное число ребер, удаление которых разрушает все нечетные циклы, равно половине максимального размера 2-упаковки нечетных циклов. [14]
Пример графа Кц убеждает, что вместо рассмотрения 2-упаковки нечетных циклов с последующим делением на 2 использовать 1-упа-ковку нечетных циклов недостаточно. Рассматривая полные графы большего размера, легко убедиться в том, что условием планарности пренебрегать нельзя. Для разрушения всех нечетных циклов из графа / LS нужно удалить 4 ребра. С другой стороны, каждый нечетный цикл имеет не менее трех ребер и, следовательно, любая Аг-упаковка нечетных циклов состоит не более чем из 10fc / 3 4fc циклов. [15]