9.4.4. Есть ли в графе эйлеров путь?

9.4.4. Есть ли в графе эйлеров путь?

Эйлеров путь и эйлеров цикл — разные вещи. Слово «цикл» подразумевает, что нужно вернуться в исходную точку. А наличие пути предполагает, что нужно лишь посетить каждую вершину ровно один раз. В следующем фрагменте демонстрируется это различие:

class Graph

 def euler_path?

  return false if !connected?

  odd=0

  each_vertex do |x|

   if degree(x) % 2 == 1

    odd += 1

   end

  end

  odd <= 2

 end

end

mygraph = Graph.new([0,1],[1,2],[1,3],[2,3],[3,0])

flag1 = mygraph.euler_circuit? # false

flag2 = mygraph.euler_path?    # true

Данный текст является ознакомительным фрагментом.