Математическое моделирование на графах. Часть 1. Берцун В.Н. - 14 стр.

UptoLike

Составители:

Рубрика:

14 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

Доказательство. При числе ребер m = 1 цикл (петля с одним

ребром) является простым. Пусть утверждение верно для циклов

длины не больше m – 1. Рассмотрим произвольный цикл С длины m.

Он либо является простым, либо проходит через некоторые верши-

ны более одного раза. На таких вершинах существует цикл длины не

больше m – 1, содержащий простой цикл. ■

Утверждение 1.4. Если у графа G все простые циклы четной

длины, то граф не имеет ни одного цикла нечётной длины.

Доказательство. 1. Если граф является простым циклом, то до-

казательство очевидно.

2. Пусть у графа с простыми циклами четной длины найдется

цикл нечетной длины. Во всяком непростом цикле нечетной длины

найдется вершина, которая повторяется более одного раза, как, на-

пример, на рис. 1.15.

Рис. 1.15

В такой вершине цикл можно разделить на два: четной и нечет-

ной длины. Будем продолжать расчленять непростые нечетные цик-

лы на четные и нечетные, пока не дойдем до простых циклов. Один

из таких циклов должен иметь нечетную длину. А это противоречит

условию, что все циклы четные. ■

Две вершины А и В графа G называются связанными, если в графе

есть цепь (путь) с концами А и В. Две вершины А и В не связаны в G,

если в графе нет ни одного пути, связывающего их. Граф называется

связным, если любые две его вершины связаны. Граф называется