Математическое описание графа множествами вершин, списками смежности и матрицей инцидентности. Суть сетки весов соответствующих неориентированным конечностям. Анализ путей отбрасывания истоков и стоков. Поиск остевого дерева алгоритмом Прима-Краскала.
Аннотация к работе
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ” Кафедра “Системного аналізу та управління” Дисципліна: „Дискретна математика” Тема: „Теорія графів.Розробка методики дослідження графу наведеного на малюнку: Провести математичний опис графу; пронумерувати вершини графу; проаналізувати граф на наявність Эйлерова циклу або Эйлерова шляху; двома алгоритмами перевірити граф на наявність циклів; знайти остовне дерево; знайти положення поліцейської дільниці; розмістити на графі магазин; вирішити задачу Дейкстри. б) програмно-розрахункова частина Розробка програмного забезпечення, яке реалізує перевірку наявності ейлерова циклу на графі, вирішає задачі Дейкстра та Флойда-Уоршала, розфарбовує граф за жадібним алгоритмом.Граф 1.1.1 Описание графа Gop множествами вершин V и дуг X 1.2 Нумерация вершин графа G «поисков в глубину» 1.2.1 Нумерация вершин графа G «поиском в ширину» 1.3.1 Для определения Эйлерова путь требуется выписать степенную последовательность вершин графа G и указать в графе G Эйлеров путьСписок использованных источниковГоворят, что ребро, принадлежащее множеству E, инцидентно вершинам, которые оно соединяет. Он полностью определяется списком вершин и указанием, какие пары вершин имеют соединяющие их ребра (в случае нагруженного графа каждому ребру или дуге еще приписывается вес). Вопросам описания графов, решению элементарных задач на графах и их программной реализации и посвящена данная работа. Данный граф может описан матрицей инцидентности вершина-ребро (нумерация вершин и ребер приведена для удобства, обычно она не пишется) Для существования Эйлерова пути допустимо только две вершины с нечетными степенями, поэтому необходимо добавить одно ребро, скажем между вершинами 4 и 7.В результате проделанной работы выполнено теоретическое обоснование для определения числовых характеристик графа, нумерации его вершин, определения числа циклов, остовного дерева и др. Разработана программа на языке Object Pascal в среде Delphi 7.0, позволяющая выполнить это в автоматизированном режиме. Заданный граф находиться как тестовый пример в папке вместе с приложением. Разработанная программа позволяет выполнить аналогичные расчеты и для графов, набранных вручную через интерфейс с использованием мыши и клавиатуры.