Нахождение всех гамильтоновых циклов заданного графа

 

 

Министерство образования и науки российской федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Юго-Западный государственный университет»

Кафедра «Вычислительной техники»

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

по дисциплине “Программирование”

на тему “ Нахождение всех гамильтоновых циклов заданного графа ”

 

Направление 230100.62 « Информационные системы и технологии» 

 

Автор работы:                         

Группа ВМ-31 Ф

 

Руководитель работы                                      

 

работа защищена:     “__”____________2014 г.

 

оценка:      _____________________

 

Председатель комиссии    _____________________

Члены комиссии:     _____________________

_____________________

 

 

 

 

Курск 2014

 

Задание на курсовой проект:

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

 

Краткая теория графов.

 

Граф, или неориентированный граф G — это упорядоченная пара G := (V, E), для которой выполнены следующие условия:

- V — это непустое множество вершин или узлов;

- E — это множество  пар (в случае неориентированного  графа — неупорядоченных) вершин, называемых рёбрами.

Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| — порядком, число рёбер |E| — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e=\{u,v\}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

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

Ребро называется петлёй, если его концы совпадают, то есть e=\{v,v\}.

Степенью \deg V вершины V называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G := (V, A), для которой выполнены следующие условия:

- V — это непустое множество вершин или узлов,

- A — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v \to w ведёт от вершины v к вершине w.

Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G := (V, E, A), где V, E и A определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного.

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

Ориентированным путём в орграфе называют конечную последовательность вершин v_i (i=1,\ldots,k), для которой все пары (v_i, v_{i+1}) (i=1,\ldots k-1) являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Граф называется:

связным, если для любых вершин u,v есть путь из u в v.

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

деревом, если он связный и не содержит простых циклов.

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

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

k-дольным, если его вершины можно разбить на k непересекающихся подмножества V_1, V_2, …, V_k так, что не будет рёбер, соединяющих вершины одного и того же подмножества.

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

планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.

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

хордальным, если граф не содержит индуцированных циклов с длиной больше трех.

Способы представления графа в информатике

Матрица смежности

Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

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

    Двумерный массив;

    Матрица с пропусками;

    Неявное задание (при помощи функции).

Матрица инцидентности

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается:

1- в случае, если связь j «выходит» из вершины i,

−1- если связь «входит» в вершину,

0 - во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким (размер пропорционален |E| |V|) для хранения, но облегчает нахождение циклов в графе.

Цикломатическое число графа — минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение: p_1(G) = p_0(G) + |E(G)| - |V(G)|, где p_1(G) — цикломатическое число, p_0 — число компонент связности графа, |E(G)| — число рёбер, а |V(G)| — число вершин.

Характеристика программного обеспечения.

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

• редактор с подсветкой синтаксиса конкретного языка программирования. В нем программист пишет текст программы, так называемый программный код;
• компилятор. Онтранслирует программу, написанную на высокоуровневом языке программирования в машинный язык (машинный код), непосредственно понятный компьютеру
• отладчик. Служит для отладки программ. Ошибки в программах допускают абсолютно все: и новички, и профессионалы - они могут быть синтаксическими (обычно они выявляются еще на стадии компиляции) и логическими. Для тестирования программы и выявления в ней логических ошибок служит отладчик.

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

Этапы написания программы в среде разработки:

• Первый этап - редактирование;
• Второй этап - предварительная (препроцессорная) обработка;
• Третий этап - компиляция;
• Четвертый этап - компоновка;
• Пятый этап - загрузка;
• Шестой этап - выполнение.

Редактирование. Это первый этап разработки программы в среде программирования и представляет он собой редактирование файла (исходного файла, который в последствии будет содержать код программы). Он выполняется с помощью редактора программ, который напоминает нам обычный текстовый редактор, такой как блокнот, word и т.д.

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

Компиляция. На этом этапе компилятором проверяется текст программы на наличие синтаксических ошибок и затем, если все хорошо, текст программы с подстановками, сделанными на предыдущем этапе, преобразуется в машинный код (код на языке, уже непосредственно понятный компьютеру). Иногда его еще называют объектным. Также в программе могут использоваться кусочки уже готового машинного кода, расположенного в иных библиотеках. На этапе компиляции эти библиотеки еще не будут подключены к только что созданному машинному коду. Они подключаются на следующем этапе.

Компоновка. Следующий этап называется компоновка. Программы могут содержать ссылки на функции, определенные где-либо вне самой программы, например, в стандартных библиотеках или в личных библиотеках групп программистов, работающих над данным проектом. Объектный код, созданный компилятором, обычно содержит «дыры» из-за этих отсутствующих частей. Компоновщик связывает объектный код с кодами отсутствующих функций, чтобы создать исполняемый загрузочный модуль (без пропущенных частей). Получаем в итоге файл с расширением .exe (для Windows), либо .out (для Linux).

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

Выполнение. С этого момента компьютер под управлением своего ЦПУ (центральное процессорное устройство) начинает последовательно выполнять в каждый момент времени по одной команде программы. Эти моменты времени носят название такт, каждый процессор имеет свою тактовую частоту, которую задает его внутренний тактовый генератор. Чем более высокая частота работы вашего процессора, тем, соответственно, лучше и тем быстрее выполняются ваши программы.

Для решения задачи по нахождению цикломатического числа графа необходима среда разработки на объектных языках программирования. Мной была выбрана BorlandDelphi 7 Enterprise.

BorlandDelphi 7 Enterprise - среда программирования на языке ObjectPascal.

Структура среды программирования.

Внешний вид среды программирования Delphi отличается от многих других из тех, что можно увидеть в Windows. Кпримеру, Borland Pascal for Windows 7.0, Borland C++ 4.0, Word for Windows, Program Manager - этовсе MDI приложенияивыглядятпо-другому, чем Delphi. MDI (MultipleDocumentInterface) - определяет особый способ управления нескольких дочерних окон внутри одного большого окна.

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

Главные составные части среды программирования.

• Дизайнер Форм (FormDesigner)
• Окно Редактора Исходного Текста (EditorWindow)
• ПалитраКомпонент (Component Palette)
• ИнспекторОбъектов (Object Inspector)
• Справочник (On-line help)

 

 

 

 

 

 

Рис.1: Дизайнер Форм - то место, где Вы создаете визуальный интерфейс программы.

 

 

 

 

 

 

 

Рис.2: В окне Редактора Вы создаете логику управления программой.

 

Рис.3: Палитра Компонент - место, где Вы выбираете объекты, которые будут помещены на вашу форму.

 

 

 

 

 

 

Рис.4: Инспектор Объектов позволяет определять свойства и поведение объектов, помещенных на форму.

 

 

 

 

 

 

 

 

Рис.5: Справочник - быстрый поиск любой информации.

В дополнение к инструментам, обсуждавшимся выше, существуют пять средств, поставляемых вместе с Delphi. Эти инструментальные средства:

• Встроенный отладчик
• Внешний отладчик (поставляется отдельно)
• Компилятор командной строки
• WinSight
• WinSpector