Определение связности графа на Лиспе

РЕФЕРАТ

Пояснительная записка к курсовой работе содержит 16 страниц, 9 рисунков, 3 источника литературы, 2 приложения.

Темой работы является написание программы на XLisp, определяющей, является ли данный неориентированный граф связным.

Целью работы является приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования, а также подготовка к выполнению дипломного проекта.

Ключевые слова: программа, алгоритм, поиск, вершина, ребро, граф, связанность, путь, список, функция.

СОДЕРЖАНИЕ

Введение

1 Анализ задачи

2 Обоснование выбора алгоритма и структур данных

3 Описание алгоритма

4 Обоснование набора тестов

Заключение

Список литературы

Приложение 1. Текст программы

Приложение 2. Результаты работы программы

ВВЕДЕНИЕ

Двоичные деревья играют весьма важную роль в теории информации.

Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

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

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

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

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

Можно привести множество примеров, неопровержимо доказывающих практическую ценность теории графов.

Темой работы является написание программы на XLisp, определяющей, является ли данный неориентированный граф связным. Целью работы является приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования, а также подготовка к выполнению дипломного проекта.

1 Анализ задачи

В данной работе необходимо написать программу на языке XLisp, определяющую, является ли данный неориентированный граф связным. Для этого необходимо запрограммировать предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.

Говорят, что задан неориентированный граф G, если заданы два множества:

- непустое множество V={v₁,..., v_n} - множество вершин графа;

- множество Q неупорядоченных пар (v_i, v_j), где v_i, v_j V. Это множество называется множеством рёбер графа. Очевидно, что (v_i, v_j) Q (v_j, v_i) Q, причем это одно и то же ребро.

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

Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах, и несвязными в противном случае.

Граф называется связным, если любые две его вершины связны, и несвязным в противном случае.

2 Обоснование выбора алгоритма и структур данных

Для определения связности графа используется поиск пути от одной вершины к другой. Граф является связным, если все вершины связаны между собой. Можно утверждать, что граф является связным, если одну из вершин можно соединить со всеми другими путем. Алгоритм определения связности графа заключается в поиске пути от первой вершины ко всем остальным. Если все пути можно найти - значит граф связный.

Поиск пути от одной вершины к другой будет выполняться по алгоритму поиска в ширину. Схема алгоритма изображена на рисунке 2.1.

Рис.2.1 - Схема алгоритма поиска в ширину

Поиск вершин, смежных с новыми вершинами выполняется так:

а) Если список ребер пустой - выход.

б) Берется первое ребро в списке ребер.

в) Если одна из вершин ребра находится в списке новых вершин, а вторая не входит ни в список новых вершин, ни в список найденных вершин, то вершина добавляется в список смежных вершин.

г) Удалить из списка ребер первое ребро и перейти к пункту а.

Граф представляется двумя множествами (списками): списком вершин и списком ребер. Каждое ребро - это список из двух вершин. Данный выбор обосновывается тем, что списки являются основным способом представления множеств данных.

3 Описание алгоритма

Были разработаны следующие функции (текст программы приведен в приложении 1).

Функция smezver (x y snaid snov) - определяет, является ли вершина y смежной с одной из новых вершин (x - входит в список новых вершин, y - не входит в списки новых и найденных вершин).

Параметры:

- x - первая вершина ребра;

- y - вторая вершина ребра;

- snaid - список найденных вершин;

- snov - список новых вершин.

Функция smez (snaid snov sreb) - поиск смежных с новыми вершинами вершин.

Параметры:

- snaid - список найденных вершин;

- snov - список новых вершин;

- sreb - список ребер.

Функция shir(snaid snov y sreb) - поиск в ширину пути.

Параметры:

- snaid - список найденных вершин;

- snov - список новых найденных вершин;

- y - вершина для поиска;

- sreb - список ребер.

Функция path(x y sreb) - поиск пути от вершины x к вершине y.

Параметры:

- x - первая вершина;

- y - вторая вершина;

- sreb - список ребер.

Функция perebor(fver sver sreb) - перебор вершин и поиск пути от первой вершины ко всем остальным.

Параметры:

- fver - первая вершина;

- sver - список вершин:

- sreb - список ребер.

Функция svgraf(sver sreb) - определение связанности графа.

Параметры:

- sver - список вершин;

- sreb - список ребер.

4 Обоснование набора тестов

При тестировании используются следующие тесты:

Рис.4.1 - Тест 1. Связанный граф

Рис. 4.2 - Тест 2. Связанный граф

Рис. 4.3 - Тест 3. Несвязанный граф

Рис. 4.4 - Тест 4. Связанный граф

Рис. 4.5 - Тест 5. Несвязанный граф

Рис. 4.6 - Тест 6. Связанный граф

Рис. 4.7 - Тест 7. Несвязанный граф

Рис. 4.8 - Тест 8. Несвязанный граф

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

При тестировании все тесты были выполнены успешно. Результаты работы программы приведены в приложении 2.

ЗАКЛЮЧЕНИЕ

В данной работе написана программа на XLisp, определяющей, является ли данный неориентированный граф связным.

Все поставленные цели выполнены: приобретены навыки и методы программирования достаточно сложных задач на языках логического программирования, а также проведена подготовка к выполнению дипломного проекта.

Программа отлажена и протестирована.

СПИСОК ЛИТЕРАТУРЫ

1 Лутай В.Н. Программирование на языках Лисп и Пролог. ТРТУ,1998.

2 Филд А., Харрисон П. Функциональное программирование. - М.: Мир, 1993.

3 Уилсон Р. Введение в теоpию гpафов. - М.: Миp, 1977.

ПРИЛОЖЕНИЕ 1

Текст программы

; смежная вершина (первая вершина ребра, вторая вершина ребра,

; список найденных вершин, список новых вершин)

(defun smezver(x y snaid snov)

(cond

((not (member x snov)) nil) ;x не является новой вершиной

((member y snov) nil) ;y является новой вершиной

((member y snaid) nil) ;y является ранее найденной вершиной

(t t))) ;вершина является новой смежной вершиной

;поиск смежных вершин (список найденных вершин, список новых вершин, список ребер)

(defun smez(snaid snov sreb)

(cond

((null sreb) nil) ;конец поиска

((smezver (caar sreb) (cadar sreb) snaid snov) ;смежная вершина

(cons (cadar sreb) (smez snaid snov (cdr sreb)))) ;добавление в список

((smezver (cadar sreb) (caar sreb) snaid snov) ;смежная вершина

(cons (caar sreb) (smez snaid snov (cdr sreb)))) ;добавление в список

(t (smez snaid snov (cdr sreb))))) ;пропуск ребра

;поиск в ширину (список найденных вершин, список новых найденных вершин,

; вершина для поиска, список ребер)

(defun shir(snaid snov y sreb)

(cond

((null snov) nil) ;не найдено ни одной новой вершины

((member y snov) t) ;вершина найдена

(t (shir (append snaid snov) (smez snaid snov sreb) y sreb)))) ;добавление новых вершин

;поиск пути (первая вершина, вторая вершина, список ребер)

(defun path(x y sreb)

(shir nil (list x) y sreb)) ;поиск в ширину

;перебор вершин (первая вершина, список вершин, список ребер)

(defun perebor(fver sver sreb)

(cond

((null sver) t) ;конец перебора

((path fver (car sver) sreb) (perebor fver (cdr sver) sreb)) ;путь найден

(t nil))) ;нет пути

;определение связанности графа(список вершин, список ребер)

(defun svgraf(sver sreb)

(perebor (car sver) (cdr sver) sreb)) ;перебор вершин и поиск пути от первой вершины ко всем остальным

ПРИЛОЖЕНИЕ 2

Результаты работы программы

Тест: 1

Выражение: (svgraf (v1 v2 v3 v4) ((v1 v2) (v2 v3) (v3 v4)))

Результат: Т

Тест: 2

Выражение: (svgraf (v1 v2 v3 v4) ((v1 v2) (v2 v4) (v2 v3) (v3 v4) (v1 v4) (v3 v4)))

Результат: T

Тест: 3

Выражение: (svgraf (v1 v2 v3 v4 v5 v6 v7) ((v1 v2)(v2 v3)(v1 v3)(v4 v5)(v4 v7)(v5 v6)(v6 v7)))

Результат: NIL

Тест: 4

Выражение: (svgraf (v1 v2 v3 v4 v5 v6) ((v1 v7)(v2 v7)(v3 v7)(v4 v7)(v5 v7)(v6 v7)(v1 v1)(v2 v2)(v3 v3)(v4 v4)(v5 v5)(v6 v6)))

Результат: T

Тест: 5

Выражение: (svgraf (v1 v2 v3 v4) ((v1 v2)(v1 v2)(v3 v4)(v3 v4)))

Результат: NIL

Тест: 6

Выражение: (svgraf (v1) nil)

Результат: T

Тест: 7

Выражение: (svgraf (v1 v2 v3) nil)

Результат: NIL

Тест: 8

Выражение: (svgraf (v1 v2 v3 v4) ((v1 v2) (v2 v3) (v3 v1)))

Результат: NIL