Размещено на http://www.allbest.ru/

Определение минимального покрытия просто графа

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

1.1 Постановка задачи

Исходными данными задачи о покрытии множества является конечное множество U и семейство S его подмножеств. Покрытием называют семейство C S наименьшей мощности, объединением которых является U. В случае постановки вопроса о разрешении на вход подаётся пара (U, S) и целое число k; вопросом является существование покрывающего множества мощности k (или менее).

Задача о минимальном (наименьшем) покрытии (ЗНП) своим названием обязана следующей теоретико-множественной интерпретации. Даны множество R = {r₁, …, r_M} и семейство ж = {S₁, …, S_N} множеств S_j R. Любое подсемейство ж' = {, , …, } семейства ж, такое, что

называется покрытием множества R, а множества S_j называются покрывающими множествами.

Если каждому S_j ж поставлена в соответствие (положительная) стоимость с_j, то ЗНП формулируется так: найти покрытие множества R, имеющее наименьшую стоимость, причем стоимость семейства ж' = {, …, } определяется как . В матричной форме, упомянутой ранее, когда строки (М N) - матрицы [t_ij], состоящей из нулей и единиц, покрываются столбцами, ЗНП может быть сформулирована как задача линейного программирования:

минимизировать z = при ограничениях, i = 1, 2, …, M,

где c_j 0, и

1.2 Выбор языка программирования

На выбор языка программирования влияют следующие факторы:

1. характер решаемой задачи;

2. имеющиеся в наличии системные библиотеки;

3. поддерживаемые компилятором платформы.

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

1. гибко работать с динамически выделяемой памятью;

2. иметь объектно-ориентированное расширение;

3. иметь средства обработки исключительных ситуаций;

4. получать высокоскоростной код.

Перечисленным требованиям удовлетворяют С++ и Паскаль. До недавнего времени Паскаль (и его диалект Delphi) значительно уступал С++ по возможности формирования высокоскоростного кода. Но теперь в компилятор Delphi 7 был встроен оптимизатор, который позволяет формировать высокоскоростной код.

Также в пользу Delphi 7 говорит и то, что он теперь может оперировать с динамическими массивами, то есть с такими массивами, количество элементов которых может меняться в процессе выполнения программы.

Borland Delphi 7 генерирует код для операционных систем Windows 9х, ХР и NT. Имеет средства визуального построения приложений.

1.3 Этапы разработки программного обеспечения

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

1) анализ требований, предъявляемых к системе;

2) определение спецификаций;

3) проектирование;

4) кодирование;

5) тестирование;

6) эксплуатация и сопровождение. [7]

На круговой диаграмме (рис. 1) показано приблизительное распределение временных затрат на реализацию отдельных этапов цикла разработки.

На первом этапе разработки систем, часто неоправданно опускаемом, определяются требования, выполнение которых позволяет получить приемлемое решение проблемы. Например, предложение «Разработать программу выписки счетов по платежной ведомости на языке КОБОЛ объемом не более 50 000 слов» не является требованием. Это лишь частная спецификация машинного решения задачи. При этом ЭВМ выступает лишь в качестве инструмента в сложной системе человек - машина, используемой для решения задачи. Анализ же требований, предъявляемых к системе, сосредоточен на интерфейсе между этим инструментом и человеком, его использующим. Например, при оплате служащих компания может рассмотреть несколько взаимоисключающих вариантов:

1. Оплата наличными.

2. Использование ЭВМ для выписки счетов.

3. Выписка счетов вручную.

4. Начисление суммы непосредственно на банковские счета служащих.

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

1. Временные затраты на реализацию этапов цикла разработки программного обеспечения (за исключением этапа эксплуатации и сопровождения)

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

Если на этапе анализа требований, предъявляемых к системе, решается вопрос о целесообразности использования ЭВМ, то на этапе определения спецификаций осуществляется точное описание функций, реализуемых с помощью ЭВМ. На этом этапе задается структура входных и выходных данных. Так, в случае примера с платежной ведомостью должны быть решены следующие вопросы: На диске или на магнитной ленте следует разместить информацию о служащих фирмы? Какими должны быть форматы записи в файле и на выходе системы? Есть ли необходимость в выдаче счетов на печать? Не следует, ли иметь отдельный диск для хранения информации о счетах, чтобы иметь возможность производить автономную распечатку? Печатать ли вместе со счетами дополнительные сведения? Какие алгоритмы необходимо применить для вычисления различного рода удержаний (налогов, страховок по безработице и медицинскому обслуживанию, отчислений на пенсионное обеспечение)?

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

2. Диаграмма цикла жизни программного обеспечения.

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

При описании цикла жизни программного обеспечения термины «требования», «спецификации», «проектирование» часто интерпретируют по-разному. Поясним принятые нами определения с помощью рис. 2.

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

КОДИРОВАНИЕ

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

ТЕСТИРОВАНИЕ

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

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

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

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

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

2. Каждая ветвь программы должна быть опробована, и программа при этом должна выдать правильные результаты.

3. Каждый путь в программе должен быть испытан хотя бы один раз с использованием набора тестовых данных, и программа должна выдать правильные результаты.

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

Хотя на первый взгляд пп. 1 и 2 могут показаться схожими, в действительности они сильно разнятся.

ЭКСПЛУАТАЦИЯ И СОПРОВОЖДЕНИЕ

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

3. Временные затраты на реализацию этапов жизненного цикла программного обеспечения (с учетом этапа сопровождения)

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

2 . Алгоритмическая часть

2.1 Задача о покрытии

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

Множество вершин графа называется независимым (или внутренне устойчивым), если никакие две вершины из этого множества не смежны. Иными словами, если S VG и S независимо в графе G, то порожденный подграф G(S) является пустым. Очевидно, что если при этом S' S, то S' - также независимое множество.

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

К отысканию наибольшего независимого множества вершин в графе сводится, например, известная задача о восьми ферзях, которую связывают с именем К. Гаусса. [6]

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

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

Число вершин в наибольшем независимом множестве графа G называется числом независимости (числом внутренней устойчивости, неплотностью) этого графа и обозначается через ₀ (G).

Например, для графа G, изображенного на рис. 6, ₀ (G')=4, множества вершин {1, 2, 3, 7}, {1, 2, 3, 8}, {2, 3, 5, 7} и {2, 3, 5, 8} являются наибольшими независимыми, а {4, 7} - максимальное независимое множество, не являющееся наибольшим.

Введем еще одно понятие, связанное с понятием независимости. Будем говорить, что вершина и ребро графа покрывают друг друга, если они инцидентны. Таким образом, ребро е = аb покрывает вершины а и b, а каждая из этих вершин покрывает ребро е. Подмножество V' VG называется покрытием (вершинным покрытием, опорой) графа G, если каждое ребро из EG инцидентно хотя бы одной вершине из V. Покрытие графа G называется минимальным, если оно не содержит покрытия с меньшим числом вершин, и наименьшим, если число вершин в нем наименьшее среди всех покрытий графа G. Число вершин в наименьшем покрытии графа G называется числом покрытия (или числом вершинного покрытия) графа G и обозначается через o(G).

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

Множество U вершин графа G является (наименьшим, минимальным) покрытием тогда и только тогда, когда U'=VG\U - (наибольшее, максимальное) независимое множество. Следовательно,

₀(G)+₀(G)= |G|.

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

Поскольку |U| + |U'| = \G\, то, очевидно, наибольшим U' соответствуют наименьшие U и наоборот. С помощью этой теоремы все приведенные выше оценки числа ₀(G) очевидным образом преобразуются в оценки для o(G). Независимое множество вершин графа имеет естественную матричную интерпретацию. Пусть X = {v₁, v₂,……, v_k} - независимое множество вершин графа G, А = A(G) - матрица смежности. Множеству Х в матрице А соответствует подматрица, элементы которой, расположенные в строках и столбцах, соответствующих элементам множества X, равны нулю. Такое представление позволяет получить верхнюю оценку числа ₀(G) с помощью характеристических чисел матрицы А. [6]

Определение числа покрытия ₀(G) и, тем более, построение наименьшего вершинного покрытия для произвольного графа G - сложные алгоритмические задачи. Эффективных алгоритмов для их решения, видимо, не существует.

Очевидно, что для каждого графа G число вершин в любом покрытии не меньше числа ребер в произвольном паросочетании, в частности,

₀(G) ₁(G)

Последние два числа могут как совпадать, так и не совпадать. Например, ₀(К₃) = 2 ₁(K₃) = 1. Для двудольного же графа эти числа всегда равны, т.е. верна следующая

Теорема 1. Для любого двудольного графа G число вершин в наименьшем вершинном покрытии равно числу ребер в наибольшем паросочетании: ₀(G) = ₁(G) Пусть G = (Х, Y, Е) - двудольный граф. Вначале предположим, что в G нет изолированных вершин. Очевидно, что для любого подмножества A X множество C = N(A) (X \ A).

является покрытием графа G. С другой стороны, пусть D - произвольное минимальное покрытие. Представим множество D в виде

D = X₁ Y₁, X₁ X, Y₁ Y

и положим А = X \ X₁. Тогда N(A) Y₁. Но как замечено выше, множество X₁ N(A) само является покрытием. Поскольку покрытие D минимально, то D = Х₁ N(А). Итак, всякое минимальное покрытие графа G имеет вид (*), и потому

Для графов без изолированных вершин теорема доказана. Очевидно, что при добавлении к графу G изолированной вершины не меняется ни ₀(G), ни ₁(G), так что теорема верна и для графов с изолированными вершинами.

Поскольку для любого графа G верны равенства ₀(G) + ₀(G) = |G| и ₁(G) + ₁(G) = |G|, то из теоремы 1 вытекает

Следствие 1. Для любого двудольного графа G верны равенства

₀(G) + ₁(G) = |G|, ₀(G) = ₁(G)

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

Как следствие из теоремы 1 получим один важный факт из теории бинарных матриц, доказанный Д. Кёнигом в 1931 году. Под линией матрицы будем понимать ее строку или столбец. Два элемента матрицы назовем независимыми, если они не лежат на одной линии.

Теорема Кёнига. Максимальное число попарно независимых единиц бинарной матрицы равно минимальному числу ее линий, содержащих все единицы матрицы.

С одной стороны, произвольная бинарная матрица А может истолковываться как приведенная матрица смежности некоторого двудольного графа G = (Х, Y, E). Тогда независимость двух единиц матрицы означает, что соответствующая им пара ребер графа G несмежна. Поэтому максимальное число независимых единиц матрицы А равно числу паросочетания ₁(G).

С другой стороны, каждой строке матрицы А соответствует вершина из X, каждому столбцу - вершина из Y, а единицам линии - ребра, инцидентные соответствующим вершинам. При этом множеству линий матрицы А, содержащих все ее единицы, соответствует множество вершин графа G, являющееся покрытием. Следовательно, минимальное число элементов в покрытиях графа G равно минимальному количеству линий матрицы А, содержащих все ее единицы. Но согласно теореме 1 число вершин в наименьшем покрытии графа G также равно ₁(G). [6]

2.2 Алгоритм определения покрытия простого графа

Простым графом называется такой граф G = (XY, Г), что

XY=0 (1)

(X_iX) ГX_iY или ГX_i=0 (2)

(Y_i)Y) Гy_i=0 (3)

Простой граф можно определить также как многозначное отображение Г конечного множества Х в конечное множество Y (возможно Х = Y).

Простой граф будем обозначать G = (X, Y, Г)

Покрытие простого графа. Покрытием простого графа G = (X, Y, Г) = (X, Y, U) называют такое подмножество дуг W с U, что любая вершина графа инцидентна по крайней мере одной дуге из W.

Для того чтобы простой граф обладал покрытием, необходимо и достаточно выполнение условий:

(X_i X) ГX_i (4)

(Y_j Y) Г-¹Y_j (5)

Например, множество

W = {(X₁, Y₁), (X₂, X₄), (X₃, Y₂), (X₄, Y₃),

(X₅, Y₄), (X₅, Y₅), (X₆, Y₃)} (6)

- покрытие простого графа на рис. 9 (на рис. 10 и 11 оно выделено).

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

Найдем минимальное покрытие Wo простого графа G = (X, Y, Г), где

Х = {X₁, X₂, …, X_m}, Y = {Y₁, Y₂, …, Y_m}

Соединим вход Хо с каждой вершиной X_i = 1, 2,…, m, дугой с пропускной способностью, равной 1, а каждую вершину Y_j = 1, 2,…, n, с выходом Y_n+1 дугой с пропускной способностью, также равной 1. Дугам (Х_i, Y_j) U припишем нулевую пропускную способность.

По методу Форда - Фалкерсона ищем минимальный поток от Хo к Y_n+1. Решение может быть не единственным. Проиллюстрируем сказанное на примере. Предварительно строим некоторый поток, для которого (u) с(u). Затем, рассматривая пути, идущие от Хо к Y_n+1, уменьшаем поток до тех пор, пока это возможно. Приходим к минимальному потоку на рис. 13. Дуги с ненулевым потоком дают минимальное покрытие Wo.

В нашем случае |Wo| = |X|; в общем же случае

|Wo| |X|, (7)

|Wo| |Y|. (8)

Например, для графа на рис. имеем

|Х|=6, |Y|=5, |Wo| = 7. (9)

Описание алгоритма, использующего булево матричное представление. Опишем алгоритм (рассматривая одновременно пример) позволяющий получить минимальное покрытие простого графа G = (X, Y, Г), представленного в виде булевой матрицы |M| размера m*n (в нашем примере в качестве |М| берется матрица).

	Y1	Y2	Y3	Y4	Y5	Fi
X1	1	1	0	0	0	2
X2	0	1	1	0	0	2
X3	0	0	1	1	1	3
X4	1	0	0	0	0	1
X5	1	0	0	1	0	2
X6	1	0	0	0	0	1
Gj	4	2	2	2	1	T=11

1) Сопоставим каждой строке X_i матрицы |М| число F_i, равное сумме ее элементов, и каждому столбцу Y - число G_j, равное сумме его элементов (на рис. 18 F_i указаны справа, а G_j внизу). Очевидно, что

(10)

2) Если (11)

то множество дуг, соответствующих единицам, дает минимальное покрытие Если

(12)

то заменяем последовательно в произвольном порядке нулем каждую из единиц (условливаясь при этом писать 1 вместо 0), для которой F_i - 1 > 0 и G_j - 1 > 0. Например, заключая в квадратик 1 на местах (X₁, Y₁), (X₂, Y₃), (X₅, Y₄) в матрице на рис. 19, приходим к матрице на рис. 20. Легко видеть, что эту операцию дальше продолжить нельзя.

3) В каждой строке с F_i > 1 ищем такую неотмеченную 1, что в содержащем ее столбце найдется такая отмеченная 1, что в строке, содержащей эту 1, есть либо неотмеченная 1 с G_j > 1, либо отмеченная 1. Если G_j > 1, то появляется возможность увеличить число отмеченных единиц. Если G_j = 1 и j-й столбец содержит отмеченную 1, то в ее строке ищем неотмеченную 1, в столбце которой есть отмеченная 1, и т.д.

3. Программная реализация

3.1 Постановка задачи на программирование

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

G = (XY, Г), что

XY=0

(XiX) ГXiY или ГXi=0

(Yi)Y) Гyi=0

При разработке программы было введено ограничение на максимальное число вершин графа - 30.

3.2 Назначение программы

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

3.3 Системные требования

Для установки требуется до 700 Кбайт на жестком диске.

Программа работает на ПК под управлением ОС Windows 95/98/Me или Windows NT/2000/XP/7.

Работа под управлением Windows 95 возможна только, начиная с версии Windows 95 OSR2 (v. 4.00.950B).

Минимальные требования программ к конфигурации ПК совпадают с таковыми для соответствующих ОС. ПК должен полностью поддерживать систему команд процессора i80386.

3.4 Последовательность проектирования

Опишем последовательность проектирования интерфейса программы.

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

Изменим некоторые свойства нашей формы.

Caption (заголовок) - «Покрытие»;

BorderIcons (кнопки в строке заголовка окна) - запретим кнопку максимизации окна: biMaximize = False;

Position (позиция окна на экране при запуске программы) - poScreenCenter.

Все остальные свойства формы оставим без изменения.

Далее приступаем к размещению элементов управления.

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

Все рабочие компоненты разместим на трех вкладках PageControl - набор панелей с закладками. Каждая панель может содержать свой набор интерфейсных элементов и выбирается щелчком по связанной с ней закладке. Чтобы на этапе конструирования добавить новую панель или выбрать ранее вставленную, щелкните по компоненту правой кнопкой мыши и выберите New page (новая панель), Next page (следующая панель) или Previous page (предыдущая панель).

Размещаем компоненты:

Для ввода матрицы смежности используется таблица TStringGrid.

Число вершин задается компонентом SpinEdit - двойная кнопка. Дает удобное средство управления некоторой числовой величиной.

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

BitBtn - командная кнопка с надписью и пиктограммой для запуска алгоритма.

Изображение графа поместим в Image - рисунок. Этот компонент предназначен для отображения рисунков, в том числе пиктограмм и метафайлов.

Метки Label - представляет собой статический текст и служит для отображения информации. В программе в них будет выводиться пояснительный текст.

Для группировки элементов ввода разместим Panel - является несущей конструкцией для размещения на ней других элементов управления, являясь в этом случае родителем для размещенных на ней компонентов. Рекомендуется использовать компонент TPanel для размещения компонентов при создании пользовательского интерфейса.

RichEdit - многострочный редактор форматированного текста (страница Win32). Текст в компоненте RichEdit подчиняется правилам Расширенного Текстового Формата (RTF - Rich Text Format) и может изменять такие свои характеристики, как шрифт, цвет, выравнивание и т.д.

Вычислительные процедуры расположим в отдельном модуле. Чтобы добавить модуль к проекту необходимо из меню File выбрать пункт New и из раскрывающегося списка выбрать команду Unit.

Константы.

Nmax = 30 - максимальное число вершин графа (модуль mp_calc).

В программе описаны два пользовательских типа данных:

Mat - двумерный массив размерности Nmax*Nmax (модуль mp_calc).

Mas - одномерный массив размерности Nmax (модуль mp_calc).

Для реализации алгоритма поиска в программе используется процедура (модуль mp_calc):

MinPokr (D, N, M)

Входные параметры:

D - исходная матрица графа;

N, M - число вершин.

Выходные параметры:

D - Решение. Множество непомеченных в результате поиска вершин образуют минимальное покрытие графа.

Вывод матрицы графа осуществляется процедурой:

Vyvod (D, N, M, f)

Входные параметры:

D - Исходная матрица графа;

N, M - число вершин;

f - Ссылка на текстовый файл.

В программе используются глобальные переменные:

N, М - число вершин графа.

Процедура FormCreate

Назначение: создание главной формы.

Процедура Xchange

Назначение: изменение числа вершин Х.

Процедура Ychange

Назначение: изменение числа вершин Y.

Процедура MinCoverClick

Назначение: определение покрытия.

Локальные переменные:

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

N, M - размерность графа.

i, j, k - счетчики.

s - служебная строка.

f - указатель на текстовый файл.

Процедура VyhodClick

Назначение: выход из программы.

Процедура MainPClick

Назначение: переход на главную вкладку.

Процедура MatrixPClick

Назначение: переход на вкладку ввода матрицы.

Процедура CalcPClick

Назначение: переход на вкладку расчета.

Для установки программ на персональный компьютер пользователя, оператору необходимо скопировать загрузочный модуль MINP.EXE с дискеты на рабочий стол или в специально созданный каталог. С помощью стандартных процедур графической оболочки Windows вынести пиктограмму на рабочий стол.

Работа программы начинается после запуска пиктограммы MINP.EXE. Подведите указатель мыши к пиктограмме и двойным щелчком левой кнопки мыши запустите программу.

В нижней части окна расположена панель с тремя вкладками. НА первой вкладке Главная вводится размерность матрицы. Количество вершин рассматриваемого графа - целое положительное число от 1 до 50.

На вкладке Матрица графа задаются элементы матрицы смежности. Значения элементов равны 1 - если i и j вершины инцидентны и 0 - в противном случае.

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

Результат выводится в окно вывода.

Для завершения работы из меню Файл выбирается пункт Выход.

Заключение

В результате выполнения курсовой работы на тему «Определение минимального покрытия простого графа» была разработана программа определения путей выполняющая следующие действия:

- ввод размерность матрицы, булеву матрицу графа;

- выводить на экран найденное покрытие;

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

Использование при разработке структурного программирования и среды Delphi позволило создать программу с удобным пользовательским интерфейсом.

Программа не требовательна к аппаратному обеспечению и может работать на компьютерах с процессором Pentium 2 и выше с графическим монитором SVGA.

В качестве операционной системы может быть использована MS-Windows.

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

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

граф программа матрица покрытие

1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. - М.: Изд - во МГТУ им. Н.Э. Баумана, 2002. -744 с.

2. Борисенко В.В. Основы программирования. - М.: Интернет-университет информационных технологий, 2005. -318 с.

3. Брауде Э.Д. Технология разработки программного обеспечения. - М.: Бином, 2004. -455 с.

4. Вельбицкий И.В. Технология программирования. - М.: Техника, 2004. -279 с.

5. Емеличев В.А. Лекции по теории графов. - М.: Наука, 1990. -384 с.

6. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения. - М.: Мир, 1982. -368 с.

7. Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975, -479 с.

8. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. -427 с.

9. Орлов С.А. Технологии разработки программного обеспечения. - М.: Диалог - Наука, 2003. -477 с.

10. Терехов А. Технология программирования. - М.: Бином, 2007. -152 с.

Размещено на Allbest.ru

...