Решение прикладных задач с помощью графов и их исследование с использованием среды программирования Delphi

Содержание

1. Введение

1.1 Актуальность

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

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

1.2  Задачи исследования

Перед нами были поставлены следующие задачи:

1. Изучить теорию графов и определить ее преимущества перед другими методами решения данной проблемы.
2. Изучить алгоритм Крускала  для построения остовного связного дерева минимального веса.
3. Проанализировать и объединить полученные знания для создания программы (модели) для решения прикладных задач с помощью графов.

1.3  Объект  исследования

Изучение теории графов и применение ее в проекте (программе), созданной в среде объектно-ориентированного программирования Delphi.

2. ОСНОВНАЯ ЧАСТЬ

2.1 Теоретическая часть

2.1.1  Введение в теорию графов.

Граф G задается с помощью пары множеств G = (V,R), где V – множество (совокупность) вершин, R – множество ребер, соединяющих пары вершин.  Обычно граф  представляют с помощью диаграммы (см. Приложения, рис. 2), на которой некоторые вершины соединены линиями (ребрами).

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

Вершины называются смежными, если их соединяет ребро.  Например, вершины V1 и V2 смежные, т.к. их соединяет ребро R12.  Ребро и любая из двух его вершин называются инцидентными. Под степенью вершины называется количество инцидентных ей ребер.

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

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

Например, в графе G можно выделить несколько  циклических маршрутов, например, V1R12V2R23V3R34V4R14V1 и V2R23V3R35V5R25V2.Маршрут называется простой цепью, если все его вершины и ребра различны. Длина маршрута равна  количеству ребер, входящих в путь. Граф считается связным, если каждая его вершина достижима из любой другой (см. Приложения, рис. 2).

Ориентированные графы. В теории графов вводится понятие орграфа –  ориентированного графа, в котором каждое ребро имеет одно направление. Такие ребра называют дугами.

Взвешенные графы.  Взвешенная сеть – это такая сеть, ребрам или

дугам которой поставлены в соответствие числовые величины.

Вес сети равен сумме весов ее ребер. 

2.1.2  Описание графа с помощью матрицы смежности.

Для наглядного представления графа используются диаграммы, а для математических расчетов удобнее использовать представление графа в форме матрицы смежности (см. Приложения,  рис. 3).[2]

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

2.1.3  Подграфы и деревья.

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат графу G. Остовной связный подграф – это подграф графа G, который содержит все его вершины и каждая его вершина достижимы из  любой другой (см. Приложения, рис. 5) .

Дерево – это граф, маршрутом которого является простая цепь. Основным связным деревом называется подграф,  включающий все вершины исходного графа G, каждая вершина которого  достижима из любой другой,  и при этом не содержащий циклов. [1]

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

Пусть в матрице смежности графа G строки нумеруются индексом n, а столбцы – индексом k, тогда элементы матрицы смежности обозначают Rnk, и связный взвешенный неориентированный граф, т.е. ребра Rnk и Rkn считаются одним и тем же ребром, и поэтому в матрице смежности необходимо не учитывать дублирующие друг друга ребра (см. Приложения, рис. 4).

Введем понятие цикломатического числа γ, показывающего, сколько ребер графа нужно удалить, чтобы в нем не осталось ни одного цикла. Цикломатическое число равно разности между количеством ребер и  количеством вершин графа, увеличенной на единицу:  γ=m – n + 1, Так количество  ребер равно 8, а количество вершин равно 5.  цикломатическое число равно 4, Это значит, что для получения остовного  связного дерева в графе G необходимо убрать четыре ребра, и тогда в нем не останется ни одного цикла (см. Приложения, рис. 2).[1]

2.2  Исследовательская часть.

2.2.1  Реализация в программе.

Для построения остовного связного дерева минимального веса используется алгоритм Крускала:

1. Первоначально каждая вершина исходного графа помещается в одно элементное подмножество, где вершины изолированы.
2. Ребра сортируются по возрастанию веса.[3]
3. Ребра последовательно включаются в остовное дерево. Существуют четыре случая:

1. обе вершины ребра не принадлежат пока ни одному множеству, тогда  они объединяются в новое множество;
2. одна из вершин принадлежит множеству, а другая нет, тогда включаем вторую в множество первой;
3. обе вершины принадлежат разным множествам, тогда объединяем множества;
4. обе вершины принадлежат одному множеству, тогда исключаем   данное ребро.[3]

4. Алгоритм заканчивает работу, когда все вершины объединяются в одно множество, при этом оставшиеся ребра не включаются в остовное дерево.                                                                                      

       Пример  остовного связного  дерева графа G (см. Приложения, рис.6).

3. ЗАКЛЮЧЕНИЕ

 3.1  Выводы

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

Было проведено исследование графа с 6-тью вершинами и с его помощью был разработан проект (программа) в среде объектно-ориентированного программирования Delphi, который явился новым способом решения прикладных задач

2.  Применение

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

3.  Перспективы

Работа будет иметь свое продолжение в дальнейшем: проект будет работать для различного количества вершин графа.  

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

1. Информатика: Учеб. Пособие для пед. Спец. высш. учеб. Заведений / А.Р. Есанян, В.И. Ефимов, Л.П. Лапицкая и др. – М.: Просвещение, 1991. – 288с.: ил.
2. Мазуркевич А. PHP: Настольная книга программиста /Александр Мазуркевич, Дмитрий Еловой. - Мн.: Новое знание, 2003. - 480 с.: ил.
3. Мозговой М.В Занимательное программирование: Самоучитель . – Санкт-Петербург.:Питер, 2004. – 208 с.: ил.
4. Фаронов В.В. Описание системы и языка программирования: Учебный курс. СПБ: Питер 2006. – 459с .: ил.

5. ПРИЛОЖЕНИЯ

Рисунок 1

Рисунок 2

Рисунок 3

Рисунок 4

Рисунок 5

Рисунок 6