Простой цикл - длина
Cтраница 1
Простой цикл длины 4 не может быть порожденным подграфом графа интервалов. [1]
Так как ЙГ2 2 является простым циклом длины 4, то мы уже сталкивались с этим трудным частным случаем. Заметим, что надграфы графа Кпп представляют собой такие графы, у которых наибольшая степень равна по крайней мере п ( ср. [2]
 |
Другой 3-унитран-зитивный граф. [3] |
Если в графе О есть вершина, не принадлежащая простому циклу длины четыре, то G - простой граф. [4]
Можно ли идеи, использованные в этой статье для подсчета числа простых циклов длин 2ft 2 и 2ft 1, развить для подсчета в графе Мура числа простых циклов длины 2ft 3 и более. Как показывает теорема 6, на этом пути возникают трудности, которые нельзя преодолеть одним лишь совершенствованием вычислительной техники. Простое, но довольно длинное доказательство теоремы 6 мы опускаем. [5]
Теорема 6.14.1. Граф Г ( X, U, Ф) является двудольным тогда и только тогда, когда любой его простой цикл четной длины. [6]
Можно ли идеи, использованные в этой статье для подсчета числа простых циклов длин 2ft 2 и 2ft 1, развить для подсчета в графе Мура числа простых циклов длины 2ft 3 и более. Как показывает теорема 6, на этом пути возникают трудности, которые нельзя преодолеть одним лишь совершенствованием вычислительной техники. Простое, но довольно длинное доказательство теоремы 6 мы опускаем. [7]
Задача состоит в подсчете надграфов графа Ктп. Так как ЙГ2 2 является простым циклом длины 4, то мы уже сталкивались с этим трудным частным случаем. Заметим, что надграфы графа Кп п представляют собой такие графы, у которых наибольшая степень равна по крайней мере п ( ср. [8]
О таком маршруте скажем, что он соединяет вершины У0 и vr r называется длиной маршрута. Замкнутый маршрут длины г 5 3 называется простым циклом длины 3, если все его вершины различны. [9]
Ясно, что каждое ребро из S определяет единственный простой цикл длины 2 / 2 1, проходящий через начало. [10]
Рассуждение такое же, как и при доказательстве теоремы 2, только теперь роль одного ребра Е из 5 играет пара Я смежных ребер из S. Любая пара Я смежных ребер из S определяет точно один простой цикл длины 2ft 2, проходящий через начало, так как существует единственная простая цепь длины ft, идущая от каждой концевой вершины пары Я до начала. Обратно, каждый простой цикл длины 2ft 2, проходящий через начало, должен содержать две простые непересекающиеся цепи длины ft, идущие от начала до вершины из 5, и еще два дополнительных ребра. Эти ребра должны принадлежать множеству S и должны быть смежными, так как простой цикл - это связный подграф степени два. Итак, v есть число пар Я и его можно получить, умножив число вершин множества 5 на число способов выбора пары ребер из d - 1 ребер, инцидентных каждой вершине. [11]
Рассуждение такое же, как и при доказательстве теоремы 2, только теперь роль одного ребра Е из 5 играет пара Я смежных ребер из S. Любая пара Я смежных ребер из S определяет точно один простой цикл длины 2ft 2, проходящий через начало, так как существует единственная простая цепь длины ft, идущая от каждой концевой вершины пары Я до начала. Обратно, каждый простой цикл длины 2ft 2, проходящий через начало, должен содержать две простые непересекающиеся цепи длины ft, идущие от начала до вершины из 5, и еще два дополнительных ребра. Эти ребра должны принадлежать множеству S и должны быть смежными, так как простой цикл - это связный подграф степени два. Итак, v есть число пар Я и его можно получить, умножив число вершин множества 5 на число способов выбора пары ребер из d - 1 ребер, инцидентных каждой вершине. [12]
Предположим, что они удовлетворяются и что граф G связен. Сначала покажем, что существует такая пара нетривиальных непересекающихся по ребрам частей Я и Н, что если Я имеет ребро в вершине а0 графа G, то Я также имеет такое ребро, и наоборот. Если имеется некоторая двусторонне-бесконечная цепь Р, то можно построить Я и Я, относя ребра из Р поочередно к каждой из частей. Если G не имеет двусторонне-беско-нечных цепей, то он должен содержать циклы, так как концевых ребер не существует. Если найдется простой цикл четной длины, то применяем предыдущее построение. Если все простые циклы имеют нечетную длину, то обозначим через С один из них. Согласно предположению, в вершине а0 на С существует ребро Е ( а0, Ь) вне С. Начиная с Е, строим простую цепь Р, непересекающуюся с С, продолжая ее насколько возможно дальше. Она может вернуться на С, или быть бесконечной, или кончаться на некотором простом цикле Сь непересекающемся с С. Ребра из С принадлежат поочередно Я и Я, и в GO имеется два Я-ребра. [13]
Предположим, что они удовлетворяются и что граф G связен. Сначала покажем, что существует такая пара нетривиальных непересекающихся по ребрам частей Я и Я, что если И имеет ребро в вершине а0 графа G, то / / также имеет такое ребро, и наоборот. Если имеется некоторая двусторопне-бесконечная цепь Р, то можно построить Н и Я, относя ребра из Р поочередно к каждой из частей. Если G ив имеет двусторопие-беско-печных цепей, то он должен содержать циклы, так как концевых ребер не существует. Если найдется простой цикл четной длины, то применяем предыдущее построение. Если все простые циклы имеют нечетную длину, то обозначим через С один из них. Согласно предположению, в вершине ао на С существует ребро Е ( а0, Ь) вне С. Начиная с Е, строим простую цепь Р, непересекающуюся с С, продолжая ее насколько возможно дальше. Она может вернуться на С, пли быть бесконечной, или кончаться на некотором простом цикле С, непересекающемся с С. Ребра пз С принадлежат поочередно II и / /, и в а0 имеется два Я-ребра. [14]
Страницы: 1