Автор статьи
Валерия
Эксперт по сдаче вступительных испытаний в ВУЗах
Связный граф называется эйлеровым, если в нем существует замкнутая цепь, содержащая все ребра. Указанную цепь называют эйлеровым циклом. Если снять требование замкнутости, граф будет называться полуэйлеров.
9. У. Гамильтон (ирландский математик и астроном) в 1859 году придумал головоломку “Кругосветное путешествие”, состоящее в следующем: каждой вершине додекаэдра приписано имя известного города. Необходимо по ребрам проложить замкнутый путь, который проходил бы через все города, причем каждый город должен встретиться ровно один раз.
В честь Гамильтона графы, в которых существуют маршруты с подобным свойством, были названы гамильтоновыми. Граф G – гамильтонов, если в нем существует простая замкнутая цепь, проходящая через все вершины графа. Указанную цепь называют гамильтоовым циклом. Если отказаться от требования замкнутости, то граф называется полугамильтоновым или полугамильтоновой цепью.
10. На обед за круглым столом приглашены гости. Требуется рассадить их так, чтобы сидящие рядом были в дружеских отношениях.
Следует рассмотреть графы, в которых вершины u и v – гости, а ребра, соединяющие вершины, говорят о “дружбе” или “не дружбе” между u и v. Гостей следует рассадить за круглым столом в таком порядке, чтобы соответствующие им вершины были последовательными вершинами некоторого гамильтонова цикла.
11. Задача Л. Эйлера о коне. Обойти ходом коня шахматную доску, посетив при этом каждую клетку ровно один раз и последним (64-м) ходом вернуться в начальную клетку.
12. Задача коммивояжера. Бродячий торговец (коммивояжер) должен посетить n пунктов. Известна стоимость проезда между любыми двумя пунктами. Требуется выбрать наиболее “дешевый” замкнутый путь, проходящий через все пункты.
Следует каждому ребру приписать некоторый “вес” (вместо стоимости). Задача состоит в нахождении гамильтонова цикла минимального веса.
О сайте
Ссылка на первоисточник:
http://agiki.ru/
Поделитесь в соцсетях: