Программирование на языке Ruby
вернуться

Фултон Хэл
Шрифт:

mygraph.remove 1,3

# Напечатать степени всех вершин: 2 2 2 2.

mygraph.each_vertex {|v| p mygraph.degree v}

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

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

vmax
возвращает вершину с наибольшим номером. Метод
degree
вычисляет степень указанной вершины, то есть количество исходящих из нее ребер.

Наконец, имеются два итератора

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 году Эйлер доказал, что это невозможно. Эта классическая задача стала первой проблемой теории графов.

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