Читать курсовая по математике: "Алгоритм распознавания единичного интервального графа" Страница 1

(Назад) (Cкачать работу)

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

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

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

Единичные интервальные графы - граф пересечений интервалов одинаковой длины.

Применение интервальных графов:

Графы интервалов рассматривались для построения моделей

в биологии [1]

- при построении модели ДНК - участки ДНК, за которые отвечают разные гены, могут пересекаться;

в археологии[1]

- при восстановлении хронологического порядка археологических находок - физические (радиоуглеродный и др.) методы дают отрезок времени, к которому могут находки принадлежать, отрезки могут пересекаться;

для транспортных потоков[1]

- задача регулирования светофором движения транспорта на перекрестке.

И т.д.

В работе [2] D. G. Corneil был предложен трехмаховый (трехпроходный) алгоритм для распознавания единичных интервальных графов. Вершины графа упорядочиваются с помощью лексикографического поиска в ширину [3] в некоторую последовательность. Полученный порядок вершин проверяется на соответствие совершенному порядку исключения вершин [4] и делается вывод о том, является ли граф единичным интервальным. Для распознавания интервальных графов были предложены различные многомаховые алгоритмы, например в работе [5] предложен шестимаховый алгоритм, а в работе [6] четырехмаховый. В некоторых случаях алгоритм с сортировкой [7] может быть более эффективным, чем лексикографический поиск в ширину.

Задачи данной работы:

Изучить алгоритм распознавания единичного интервального графа с помощью трех проходов алгоритма лексикографического поиска. Изучить алгоритм 4-махов для распознавания интервальных графов. Реализовать алгоритмы в виде компьютерной программы. Провести тестовые расчеты на графах (на корректность алгоритмов и на время

Похожие работы