Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Определение наличия эйлеровых и гамильтоновых циклов

Теоретические сведения

Связный граф С называется эйлеровым, если в нем существует цикл, содержащий все ребра графа ровно по одному разу. Если граф С обладает эйлеровым циклом, то он является связным, а все его вершины — четными. Таким образом, существует очень простой критерий, позволяющий определить, является ли граф эйлеровым. Если граф С — связный и все его вершины имеют четную степень, то он имеет эйлеров цикл.

Оценка минимального числа ребер т*, удаление которых делает граф эйлеровым, в общем случае всегда производится на основе количества нечетных вершин п* по формуле

  • * п* т* > —.
  • (2.3)

Важно отметить, что не может возникнуть ситуации, при которой п* — число нечетное, так как суммарная степень вершин графа всегда четная, а значит, вершин с нечетными степенями всегда четное число.

Формула (2.3) дает именно нижнюю оценку, в реальности может возникнуть ситуация, когда необходимо удалить больше ребер, как, например, в задаче 2.104. Можно построить и другие графы, иллюстрирующие значительное превышение т* над п*, однако в любом случае оценкой сверху будет общее количество вершин графа, уменьшенное на единицу.

Граф (7 называется гамильтоновым, если в нем существует цикл, содержащий все вершины графа ровно по одному разу. Известны два критерия, позволяющие определить наличие гамильтонова цикла в графе. Если в простом графе с п вершинами, причем п > 3, выполняется условие 5(у) > п/2 для любой вершины у, то граф (7 является гамильтоновым. Пусть п — количество вершин в данном графе. Если для любой пары несмежных вершин (у,, уу) выполнено неравенство 5(у,) + 5(Уу) > п, то граф является гамильтоновым. Недостаток обоих критериев состоит в том, что даже если ни одно из этих условий не выполняется, граф может оказаться гамильтоновым.

Задачи

Задача 2.104. Определить, является ли граф (рис. 2.20) эйлеровым, и если нет — указать с достаточным обоснованием, удаление какого минимального числа ребер делает граф эйлеровым.

Решение.

Первое, что необходимо сделать, — это проверить критерий эйле-ровости, а именно четность вершин графа. Как видно из рис. 2.20, а, в графе из п = 14 вершин две имеют нечетную степень. Удобно при решении задач на рисунке заштриховать вершины, которые имеют нечетную степень. Поскольку удаление одного ребра может изменить степень двух вершин, то, если удалять попарно несмежные ребра, соединяющие только нечетные вершины, минимально возможное количество таких кандидатов на удаление будет 2/2 = 1. Нужно пробовать найти попарно несмежные ребра, соединяющие именно вершины нечетной степени. В данном случае это невозможно, поэтому, начиная с правой нечетной вершины, удаляем горизонтальные центральные ребра, пока не дойдем до левой нечетной вершины

Этапы решения задачи 2.104

Рис. 2.20. Этапы решения задачи 2.104: а — исходный граф; б — в графе отмечены вершины нечетной степени;

в — граф после удаления ребер

(рис. 2.20, в). Таким образом, хотя у исходного графа было только две вершины нечетной степени, для того чтобы граф стал эйлеровым, необходимо удалить пять ребер.

Задача 2.105. Является ли эйлеровым регулярный граф:

  • а) степени 4 на 11 вершинах;
  • б) степени 3 на 12 вершинах?

Задача 2.106. Является ли эйлеровым полный граф:

  • а) на 17 вершинах;
  • б) на 18 вершинах?

Задача 2.107. Какими должны быть степени всех вершин графа, чтобы в нем существовал эйлеров цикл?

Задача 2.108. Какое минимальное число ребер надо удалить из полного графа:

  • а) на пяти вершинах;
  • б) на четырех вершинах, чтобы он стал эйлеровым?

Задача 2.109. Является ли гамильтоновым простой цикл на 17 вершинах?

Задача 2.110. Можно ли построить гамильтонов граф с 16 ребрами на 17 вершинах?

Задача 2.111. Является ли эйлеровым регулярный граф степени 3 на 12 вершинах?

Задача 2.112. Является ли гамильтоновым полный граф:

  • а) на 17 вершинах;
  • б) на 18 вершинах?

Задача 2.113. В полных графах на скольких вершинах всегда есть эйлеров цикл?

Задача 2.114. В каких графах всегда существуют и эйлеров, и гамильтонов циклы и они совпадают?

Задача 2.115. Какой цикл (никакой, гамильтонов, эйлеров или оба) всегда есть:

  • а) в полном графе на семи вершинах;
  • б) в полном графе на 10 вершинах;
  • в) в регулярном графе степени 3 на семи вершинах?

Задача 2.116. Какой цикл (никакой, гамильтонов, эйлеров или оба) всегда есть в полном двудольном графе:

  • а) К71;
  • б) к3,7;
  • в) К2 9;
  • Г) *8,8?

Задача 2.117. Пусть G — связный граф, в котором есть точно две вершины нечетной степени. Имеет ли он эйлеров цикл? Имеет ли он эйлерову цепь? Обоснуйте ответ.

Задача 2.118. Сколько гамильтоновых циклов существует в полном графе на 2, 3, 4 вершинах? Попробуйте сформулировать ответ на общий вопрос: сколько гамильтоновых циклов существует в полном графе на п вершинах?

Задача 2.119. Построить не эйлеров, но гамильтонов граф на восьми вершинах, число базисных циклов которого равно шести, про вершины которого известно, что две вершины имеют степень 4, а степени остальных вершин одинаковы, или дать обоснованный ответ о невозможности построения такого графа.

Задача 2.120. Построить граф, являющийся одновременно эйлеровым и гамильтоновым, у которого ребер в два раза больше, чем вершин, а цикломатическое число равно шести, или дать обоснованный ответ о невозможности построения такого графа.

Задача 2.121. Построить граф, не являющийся ни эйлеровым, ни гамильтоновым, у которого ребер на одно больше, чем вершин, а цикломатическое число равно двум, или дать обоснованный ответ о невозможности построения такого графа.

Задача 2.122. Построить эйлеров, но не гамильтонов граф на 11 вершинах, число базисных циклов которого равно шести, про вершины которого известно, что восемь вершин имеют степень 2 и две вершины — степень 4, или дать обоснованный ответ о невозможности построения такого графа.

Задача 2.123. Для заданного графа (рис. 2.21) определить с достаточным обоснованием:

  • а) является ли граф гамильтоновым, и если да — указать гамильтонов цикл;
  • б) является ли граф эйлеровым, и если да — указать эйлеров цикл; если нет — указать с достаточным обоснованием минимальное количество и название ребер, удаление которых делает граф эйлеровым.

Задача 2.124. Для заданного графа (рис. 2.22) определить с достаточным обоснованием:

  • а) является ли граф гамильтоновым, и если да — указать гамильтонов цикл;
  • б) является ли граф эйлеровым, и если да — указать эйлеров цикл; если нет — указать с достаточным обоснованием минимальное количество и название ребер, удаление которых делает граф эйлеровым.
Условие задачи 2.124

Рис. 2.22. Условие задачи 2.124

Задача 2.125. Проверить, существует ли среди связных графов, имеющих 11 вершин, причем расстояние между любыми двумя несмежными вершинами равно двум, эйлеров, но не гамильтонов граф и гамильтонов, но не эйлеров граф. Если да — построить его (их), если нет — дать обоснование его (их) отсутствия.

Задача 2.126. Проверить, существует ли среди связных графов, имеющих десять вершин и 15 ребер, эйлеров граф. Если да — построить его, если нет — дать обоснование его отсутствия.

Задача 2.127. Проверить, существует ли гамильтонов граф среди связных графов на 21 вершине с 37 ребрами, причем 15 вершин имеют степень 4, четыре вершины — степень 3. Если да — построить его, если нет — дать обоснование его отсутствия.

Задача 2.128. Проверить, существует ли эйлеров граф среди связных графов на 15 вершинах с 26 ребрами, причем шесть вершин имеют степень 6, семь вершин — степень 2. Если да — построить его, если нет — дать обоснование его отсутствия.

Задача 2.129. Проверить, существует ли среди графов, полученных удалением произвольных 23 ребер из полного двудольного графа Кхз ід, эйлеров граф. Ответ обосновать.

Задача 2.130. Проверить, существует ли среди связных графов, имеющих шесть вершин и десять ребер, эйлеров граф. Если да, то привести его. Если нет — обосновать ответ.

Задача 2.131. Проверить, существует, ли среди связных графов, имеющих 47 ребер и 25 вершин, из которых 21 вершина имеет степень 4, а три — степень 3, гамильтонов граф. Если да, то указать его.

Задача 2.132. Проверить, существует ли среди связных графов, имеющих шесть вершин и девять ребер, эйлеров граф. Если существует, указать его. В противном случае дать обоснование его отсутствия.

 
<<   СОДЕРЖАНИЕ   >>