Скачать исходный код
Скачать все файлы проекта ГРАФОМАНИЯ
Аннотация
Рассмотрены алгоритмы на графах и множествах. Неформальное изложение алгоритмов сопровождается работающим кодом c контрольными примерами, доведенными до числа. Код воплощен на объектно-ориентированном языке программирования Delphi. Подробно описана техника программирования, а листинги детально прокомментированы. Книга может служить дополнением к учебникам по дискретной математике и справочником по алгоритмам. Она будет полезна студентам, аспирантам и программистам, решающим практические задачи в этой области.
Предисловие
Графомания — мучительная хворь, симптом которой выражен в неодолимой тяге к маранию бумаги. Замечено, что поражает она организмы, ослабленные математикой. Иначе чем ещё объяснить обилие книг под общим названием «Теория графов»? Почти все они сочинены математиками для математиков. Иные написаны математиками для простых смертных: инженеров, студентов, и любознательных пенсионеров. А поскольку эти книги от математиков, там не обходится без теорем и доказательств. Впрочем, отбросим шутки, и снимем шляпы перед талантами, коим мы обязаны этим украшением дискретной математики, тесно примыкающим к информатике и программированию.
Однако любую теорию прилагают, в конце концов, к практике. И то, что родилось в голове математика, когда-нибудь попадает в голову программиста и становится (если повезёт) работающей программой. На этом пути программист одолевает массу своих проблем: ищет оптимальные структуры данных, строит иерархию объектов, процедур и функций. При всём уважении к математике, он вынужден направлять усилия не на теоремы и доказательства, а на эти технические детали. Разумеется, что программист обязан ясно представлять воплощаемый в программу алгоритм, понимать основные идеи, лежащие в его основе, и без математической литературы ему не обойтись. И всё же книга, задуманная программистом для программистов, ему не повредит.
Итак, цель этой книги — ознакомить программиста с идеями решений задач на графах, а также с техникой кодирования этих задач. Идеи излагаются неформально, без теорем и доказательств (взамен чего даются ссылки на литературу). Потому книгу можно трактовать и как популярную теорию графов.
И всё же программирование, как и математика, — дисциплина строгая и точная. Потому словесные рассуждения здесь дополнены работающим, практически «боевым» кодом. Этот подробно прокомментированный код служит лишним пояснением: так, детали, не вполне понятные в словесном изложении, могут проясниться читателю при изучении листингов. Потому при написании кода автор стремился сделать его в первую очередь понятным и наглядным, отдавая эффективности второе место (но не последнее).
Код написан на языке Pascal, точнее, на том его диалекте, что нынче зовётся Delphi. И тому есть, по меньшей мере, две причины. Во-первых, язык Pascal распространён в образовании, стало быть, многим знаком. К тому же он так прост, что листинг поймёт и тот, кто пишет на других языках. Во-вторых, Delphi-версия языка оснащена мощным объектно-ориентированным аппаратом, как нельзя лучше подходящим для воплощения излагаемых идей. Надеюсь, что при должном понимании материала книги, читатель без особого труда переведёт код на любой нужный ему язык. Замечу, кстати, что задачи на графах — те ещё загогулины — прекрасный полигон для обретения опыта объектно-ориентированного программирования (ООП). Почему бы не воспользоваться им?
В тщетных попытках объять необъятное, автор смог привести здесь лишь часть наиболее «популярных» алгоритмов на графах, вот краткий перечень этих задач и сопутствующего материала:
Знакомство с объектами, отношениями и множествами
Представление объектов в языке Delphi
Представление множеств, операции с множествами
Понятие о сложности (трудоёмкости) алгоритмов
Задачи на множествах:
• разбиение множества на подмножества;
• задача о наименьшем разбиении (ЗНР);
• задача о наименьшем покрытии (ЗНП).
Представление отношений графами
Программная реализация графов, ввод и вывод графов
Группа задач на достижимость:
• взаимная достижимость вершин;
• кратчайшие пути между вершинами;
• выделение сильно связанных компонент.
Группа задач на размещение:
• независимые вершины и клики;
• доминирующие множества;
• раскраски;
• центры;
• p-центры;
• p-медианы.
Остовные деревья
Группа задач о потоках:
• максимальный поток в сети;
• поток, ограниченный сверху и снизу;
• минимальная стоимость потока.
Паросочетания:
• паросочетание в двудольном графе;
• паросочетание в произвольном графе.
Цикл Эйлера и задача почтальона:
• на неориентированном графе;
• на орграфе.
Задачи Гамильтона и коммивояжёра:
• разомкнутая задача Гамильтона;
• замкнутая задача Гамильтона (контур);
• комбинирование методов для задач Гамильтона.