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 (http://raa.ruby-lang.org) или на сайте Rubyforge (http://rubyforge.org). Называются они как-то вроде RubyGraph, RGraph, GraphR и по большей части еще не достигли зрелости.
Если вас интересует великолепный пакет GraphViz, который умеет представлять сложные графы в виде изображений или программ на языке Postscript, то к нему есть по меньшей мере два работоспособных интерфейса. Есть даже элемент управления GnomeGraphWidget, который, если верить документации, «можно использовать в приложениях Ruby Gnome для генерирования, визуализации и манипулирования графами». Мы его, впрочем, не изучали; пока еще не вышла даже официальная альфа- версия.
Короче говоря, потребность в подобных инструментах может возникнуть. В таком случае я призываю вас написать собственный инструмент или присоединиться к какому-нибудь существующему проекту. Если работать с графами станет достаточно просто, то мы еще будем недоумевать, как раньше могли без них обходиться!..
9.5. Заключение
Мы познакомились с классом Set в Ruby, а также с несколькими примерами «доморощенных» структур данных. Мы видели, как можно создавать сложные структуры данных путем наследования существующему классу или ограниченного делегирования, когда экземпляр существующего класса инкапсулируется в новой структуре. Также были рассмотрены изобретательные способы хранения данных, применения различных структур данных и создания итераторов для обхода таких структур.
Мы уделили внимание стекам и очередям и способам их использования для решения задач. Кроме того, окинули беглым взглядом деревья и графы.
В следующей главе мы снова займемся манипулированием данными. Но если до сих пор нас интересовало хранение объектов в основной памяти, то теперь мы обратимся к вспомогательной памяти, то
