Книга: Программирование на языке Ruby

9.4.3. Есть ли в графе эйлеров цикл?

9.4.3. Есть ли в графе эйлеров цикл?

Иногда нужно знать, есть ли в графе эйлеров цикл. Термин связан с математиком Леонардом Эйлером, который основал область топологии, занимающуюся этим вопросом. (Графы, обладающие таким свойством, называют иногда уникурсивными, поскольку их можно нарисовать не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру.)

В немецком городе Кенигсберг был остров посередине реки. С двумя берегами остров связывало семь мостов. Горожане хотели знать, можно ли обойти город так, чтобы побывать на каждом мосту ровно один раз и вернуться в исходную точку. В 1735 году Эйлер доказал, что это невозможно. Эта классическая задача стала первой проблемой теории графов.

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

class Graph
 def euler_circuit?
  return false if !connected?
  for i in 0..@max
   return false if degreed) % 2 != 0
  end
  true
 end
end
mygraph = Graph.new([1,0],[0,3],[2,1],[3,1],[3,2])
flag1 = mygraph.euler_circuit? # false
mygraph.remove 1,3
flag2 = mygraph.euler_circuit? # true

Оглавление книги