Реализация алгоритмов раскраски графа с помощью компьютера с помощью дэлфи

Оглавление

Введение 2

Глава 1. Интегрированная среда разработки приложений VBA 4

1.1. Сравнительный анализ существующего программного обеспечения 4

2.1. Представление информации в форме графа 4

2.2. Основные понятия и определения 5

2.3. Представление графов в компьютере 8

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

2.3.2. Матрица инцидентности 9

Введение

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

Этот класс задач удобен для тем, что:

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

• указывается число вершин графа и перечисляются его ребра (для ориентированных графов – дуги); в некоторых случаях задается также функция на ребрах, которая может по смыслу соответствовать цвету или весу ребер (в общем случае, с каждым ребром ассоциируется некоторая дополнительная информация);

• таких задач достаточно много.

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

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

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

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

В данной работе разработана программа реализации раскраски графа с помощью программы Delphi.