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

Наконец, имеются два итератора each_vertex и each_edge, которые позволяют перебрать все вершины и все ребра соответственно.

9.4.2. Является ли граф связным?

Не все графы связные. Иногда нет способа «добраться из одной точки в другую», то есть между двумя вершинами нет никакого пути, составленного из ребер. Связность — это важное свойство графа, его надо уметь вычислять. В связном графе любая вершина достижима из любой другой.

Не будем объяснять принцип работы алгоритма, интересующийся читатель может найти описание в любой книге по дискретной математике. Но в листинге 9.4 приведена его реализация на Ruby.

Листинг 9.4. Выяснение того, является ли граф связным

 class Graph

  def connected?
  x = vmax
  k = [x]
  l = [x]
  for i in 0..@max
  l << i if self[x,i]==l
  end
  while !k.empty?
  y = k.shift
  # Теперь ищем все ребра (y,z).
  self.each_edge do |a,b|
  if a==y || b==y
  z = a==y ? b : a
  if !l.include? z
  l << z
  k << z
  end
  end
  end
  end
  if l.size < @max
  false
  else
  true
  end
  end
 end

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

 puts mygraph.connected? # true

 puts mygraph.euler_path? # true

 mygraph.remove 1,2
 mygraph.remove 0,3
 mygraph.remove 1,3

 puts mygraph.connected? # false

 puts mygraph.euler_path? # false

В примере упомянут метод euler_path?, с которым мы еще не встречались. Он определен в разделе 9.4.4.

Можно было бы усовершенствовать этот алгоритм, так чтобы он находил все связные компоненты несвязного графа. Но мы не станем этого делать.

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

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

9.4.5. Инструменты для работы с графами в Ruby

В сообществе пользователей Ruby известно несколько таких инструментов. Они в большинстве своем имеют ограниченную функциональность и предназначены для работы с ориентированными или неориентированными графами. Поищите эти инструменты в архиве RAA или на сайте Rubyforge . Называются они как-то вроде RubyGraph, RGraph, GraphR и по большей части еще не достигли зрелости.