Color map map) color map) (paintmapwithcolor color map)))))

 

Наконец, собственно тело программы

>(defun paintall (map color)

(progn

(paintmapwithcolor color map)

(if (unpaintedyet map) (paintall map (+ 1 color)) map)))

 

 

Контрольный пример.

>(setq map '((a 0 (b c g h e))

(b 0 (a c e))

(c 0 (b a e f d))

(d 0 (c e f i j))

(e 0 (a b c d f g h i))

(f 0 (c d e h i j))

(g 0 (a e h))

(h 0 (a e f g i))

(i 0 (c d e f j h))

(j 0 (d f i))

)

)

 

((A 0 (B C G H E)) (B 0 (A C E)) (C 0 (B A E F D)) (D 0 (C E F I J)) (E 0 (A B C D F G H I)) (F 0 (C D E H I J)) (G 0 (A E H)) (H 0 (A E F G I)) (I 0 (C D E F J H)) (J 0 (D F I)))

> (paintall map 1)

((A 1 (B C G H E)) (B 2 (A C E)) (C 3 (B A E F D)) (D 1 (C E F I J)) (E 4 (A B C D F G H I)) (F 2 (C D E H I J)) (G 2 (A E H)) (H 3 (A E F G I)) (I 5 (C D E F J H)) (J 3 (D F I)))

 

Таким образом, для раскраски графа нам понадобилось пять цветов. Результат выполнения программы приведён на рисунке:

 

Задания для лабораторной работы

 

1. Дана схема метрополитена, найти кратчайший путь между станциями.

Схема метрополитена задаётся с помощью матрицы смежности или матрицы инциденций. Каждому перегону соответствует некоторый вес (длительность перегона). Каждой пересадке также соответствует некоторый вес (длительность пересадки). Необходимо для заданной преподавателем схемы вывести самый короткий путь или все такие пути, если их несколько.

 

2. Игра в 15.

Задача состоит в том, что на прямоугольном поле 4х4 расставлены прямоугольные фишки с номерами от 1 до 15 в произвольном порядке, также имеется одно пустое поле. За каждый ход можно передвинуть на пустое поле одну фишку. Задача игры состоит в том, чтобы упорядочить фишки по номерам от 1 до 15. Обратите внимание, что не для всех начальных состояний задача имеет решение. Начальная позиция вводится преподавателем и программа должна вывести наикратчайший алгоритм решения задачи, или все такие алгоритмы, если их несколько, или сообщить, что таких алгоритмов нет.

 

3. Задача о 8-ми ферзях.

Необходимо расставить на шахматной доске 8 ферзей в соответствии со стандартными правилами, так, чтобы никакие два ферзя не били друг друга (ферзь бьёт любую фигуру, находящуюся с ним на одной вертикали, горизонтали и диагонали)

 

4. Задача о 8-ми ферзях 2.

Необходимо расставить на шахматной доске фигуры, которые сочетают в себе одновременно свойства ладьи и коня и определить, какое наибольшее число таких фигур можно расставить на доске 8х8 (ладья бьёт любую фигуру, находящуюся с ней на одной вертикали или горизонтали, конь бьёт любую фигуру находящуюся через две клетки по горизонтали или вертикали и одну клетку по диагонали)

 

5. Задача о Ханойской башне.

Имеются три стержня, на один из них нанизано n дисков, остальные пустые. Диски имеют различный диаметр, упорядоченный от самого узкого наверху до самого широкого внизу. Разрешается перекладывать диски с одного стержня на другой, при условии, что ни при каких обстоятельствах более широкий диск не будет лежать сверху на более узком. Необходимо вывести последовательность действий, при которой пирамида будет перенесена с одного стержня на другой[6].

 

6. Задача о составлении расписания

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

 

7. Раскрасить плоскую карту четырьмя цветами, так что бы любые две смежные области не были окрашены в один цвет

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

.

8. Задача о коммивояжере.

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

 

9. Нахождение центральной вершины орграфа

Дан некоторый связный ориентированный граф. Необходимо найти в нём центральную вершину (наиболее равноудалённую ото всех остальных). Наиболее равноудалённая вершина может быть получена как вершина, среднее расстояние от которой до других вершин наиболее близко к среднему значению этой величины для всех вершин графа. Если таких вершин несколько, вывести их все.

 

10. Нахождение центральной вершины неориентированного графа

Дан некоторый связный неориентированный граф. Необходимо найти в нём центральную вершину (наиболее равноудалённую ото всех остальных). Наиболее равноудалённая вершина может быть получена как вершина, среднее расстояние от которой до других вершин наиболее близко к среднему значению этой величины для всех вершин графа. Если таких вершин несколько, вывести их все.

 

11. Нахождение минимально функционирующего сегмента сети.

Дана некоторая сеть (в виде графа). Каждой её дуге сопоставлена некоторая пропускная способность. Также две вершины помечены как источник и приёмник данных. Необходимо определить, какой минимальный фрагмент этой сети обладает той же пропускной способностью между источником и приёмником, что и исходная сеть.

 

12. Построить остовное дерево минимальной стоимости для произвольного неориентированного связного графа

Остовным деревом для графа называется любое свободное дерево, являющееся его подграфом. Под стоимостью понимается совокупный вес всех оставшихся в этом подграфе дуг. Необходимо для заданного неориентированного графа вывести все его остовные деревья минимальной стоимости.

 

13. Для заданного орграфа определить минимальный набор узлов, удаление которых (вместе с входящими или исходящими рёбрами) приведёт к разделению исходного графа на заданное число подграфов.

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

 

14. Для заданного неориентированного графа определить минимальный набор узлов, удаление которых (вместе с входящими или исходящими рёбрами) приведёт к разделению исходного графа на заданное число подграфов.

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

 

15. Необходимо определить степень связности орграфа

Под степенью связности графа понимается некоторое число R, такое, что между любыми двумя узлами графа имеются не менее R путей

 

16. Необходимо определить степень связности неориентированного графа

Под степенью связности графа понимается некоторое число R, такое, что между любыми двумя узлами графа имеются не менее R путей

 

17. Задача о триангуляции многоугольника.

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

 

18. Построить дерево игры в крестики-нолики на доске MхM

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

 

19. Определить, является ли заданный граф свободным деревом

Свободное дерево – дерево, не содержащее циклов

 

20. Вывести в произвольном орграфе все имеющиеся циклы без дублирования