РЕФЕРАТ
Пояснительная записка к курсовой работе содержит 16 страниц, 9 рисунков, 3 источника литературы, 2 приложения.
Темой работы является написание программы на XLisp, определяющей, является ли данный неориентированный граф связным.
Целью работы является приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования, а также подготовка к выполнению дипломного проекта.
Ключевые слова: программа, алгоритм, поиск, вершина, ребро, граф, связанность, путь, список, функция.
СОДЕРЖАНИЕ
Введение
1 Анализ задачи
2 Обоснование выбора алгоритма и структур данных
3 Описание алгоритма
4 Обоснование набора тестов
Заключение
Список литературы
Приложение 1. Текст программы
Приложение 2. Результаты работы программы
ВВЕДЕНИЕ
Двоичные деревья играют весьма важную роль в теории информации.
Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось. Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика, на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Можно привести множество примеров, неопровержимо доказывающих практическую ценность теории графов.
Темой работы является написание программы на XLisp, определяющей, является ли данный неориентированный граф связным. Целью работы является приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования, а также подготовка к выполнению дипломного проекта.
Анализ задачи
В данной работе необходимо написать программу на языке XLisp, определяющую, является ли данный неориентированный граф связным. Для этого необходимо запрограммировать предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.
Говорят, что задан неориентированный граф G, если заданы два множества:
- непустое множество V={v1,..., vn} - множество вершин графа;
- множество Q неупорядоченных пар (vi, vj), где vi, vj Î V. Это множество называется множеством рёбер графа. Очевидно, что (vi, vj) Î Q Û (vj, vi) Î Q, причем это одно и то же ребро.
Путем от vi до vj называется такая последовательность ребер графа, ведущая от vi к vj, в которой два соседних ребра имеют общую вершину и никакое ребро не встречается дважды.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах, и несвязными в противном случае.
Граф называется связным, если любые две его вершины связны, и несвязным в противном случае.
Обоснование выбора алгоритма и структур данных
Для определения связности графа используется поиск пути от одной вершины к другой. Граф является связным, если все вершины связаны между собой. Можно утверждать, что граф является связным, если одну из вершин можно соединить со всеми другими путем. Алгоритм определения связности графа заключается в поиске пути от первой вершины ко всем остальным. Если все пути можно найти – значит граф связный.
Поиск пути от одной вершины к другой будет выполняться по алгоритму поиска в ширину. Схема алгоритма изображена на рисунке 2.1.
Рис.2.1 – Схема алгоритма поиска в ширину
Поиск вершин, смежных с новыми вершинами выполняется так:
а) Если список ребер пустой – выход.
б) Берется первое ребро в списке ребер.
в) Если одна из вершин ребра находится в списке новых вершин, а вторая не входит ни в список новых вершин, ни в список найденных вершин, то вершина добавляется в список смежных вершин.
г) Удалить из списка ребер первое ребро и перейти к пункту а.
Граф представляется двумя множествами (списками): списком вершин и списком ребер. Каждое ребро – это список из двух вершин. Данный выбор обосновывается тем, что списки являются основным способом представления множеств данных.
Описание алгоритма
Были разработаны следующие функции (текст программы приведен в приложении 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 - список ребер.