Книга: Программирование на языке Ruby
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
Оглавление книги
Похожие страницы
- 9.4.2. Является ли граф связным?
- 9.4.3. Есть ли в графе эйлеров цикл?
- Глава 1. Для чего нужен «Путь Samsung»?
- Шесть рычагов полезности
- Есть ли быстрый способ доступа к папкам?
- Есть ли возможность установить пароль на папку или файл?
- Я плохо вижу, но знаю, что в Windows XP есть программная лупа. Как ее можно добавить?
- Мне требуется информация с сайта, который я посещал позавчера, но я не помню его адрес. Есть ли способ его узнать?
- Изображение на мониторе стало нечетким. Нужно нести в ремонт или есть альтернатива?
- На всех дисках моего компьютера есть папка System Volume Information. Для чего она нужна?
- На старом компьютере нужно переустановить систему, но при этом сохранить драйверы. Есть возможность «вырвать» их из сист...
- У файла и каталога есть атрибуты (например: Скрытый, Только чтение). Как ими управлять из командной строки?