Метрические характеристики графов

Федеральное агентство по образованию Воронежский государственный технический университет Кафедра САПРИС Курсовая работа По дисциплине Дискретная математика Тема:«определение метрических характеристик ориентированных и неориентированных графов» Выполнила студентка группы ИС-061 Бескоровайная М.А. Руководитель Белецкая С.Ю. Воронеж 2007 Замечания руководителя Содержание: Введение… 1.Основные понятия теории графов… 1. Способы задания графов… 2. Метрические характеристики графа… 3. Описание программы…1. Назначение… 3.2 Выбор средств реализации….3. Структура программы…4. Описание алгоритма программы… 5. Характеристика входных и выходных данных………… 15 3.6. Контрольный пример….15 Заключение… 17 Список литературы … 18 Листинг программы… 19 Введение В последнее время исследования в областях, традиционно относящихся к дискретной математике, занимают все более заметное место.

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

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

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

История возникновения теории графов.Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач. 1. Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов.

Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году. рис. 2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости.Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году. рис. 3. Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой.

Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок.В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера.

Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является.Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей.

Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая.Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

Рис. 1.Основные понятия Графом G=(X,U) будем называть совокупность двух конечных множеств: множества вершин Х={х1,…,хn} и множества ребер (дуг) U={u1,…,um}, состоящего из некоторых пар элементов (хi,xj) множества Х. Геометрически граф может быть представлен в виде рисунка, в котором вершинам соответствуют точки, а ребрам - линии, соединяющие все или некоторые из этих точек.

Граф называется помеченным, если его вершинам приписаны некоторые метки, например, номера.Если пары вершин(xi,xj) во множестве U являются неупорядоченными (т.е. порядок соединения вершин не существенен), то граф называется неориентированным (неографом), а пары (хi,хj) ребрами этого графа (рис.1). При этом вершины xi,xj называют концами (концевыми вершинами) ребра. В данном случае также говорят, что ребро (хi,хj) соединяет вершины хi и хj. Если пары вершин (хi,хj) во множестве U являются упорядоченными (т.е порядок соединения вершин существенен), то граф называется ориентированным (орграфом), а пары (хi,хj) - дугами (рис.2). Дуги орграфа, в отличие от ребер неографа, будем обозначать <хi,хj > . При этом хi- начало (начальная вершина) дуги, хj - конец (конечная вершина) дуги. Говорят также, что дуга <хi,хj > исходит из вершины хi и заходит в вершину хj. Заметим, что <хi,хj > и <хj,хi > - это различные дуги в графе.

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

Пара вершин хi,хj может соединяться двумя или более ребрами (дугами одного направления). Такие ребра (дуги) называют кратными.Количество одинаковых ребер (хi,хj) (дуг <хi,хj>) называется кратностью соответствующего ребра (дуги). Петлей называется дуга (ребро), с совпадающими начальной и конечной вершинами.

Граф с петлями и кратными ребрами(дугами) называется псевдографом. Граф с кратными ребрами(дугами) и без петель называется мультиграфом. Граф, не содержащий петель и кратных ребер называется простым графом.Так, граф, представленный на рисунке 1 является псевдографом, так как содержит петлю (X4,X4) и кратное ребро (X1,X2). Граф на рисунке 2 является мультиграфом, граф на рисунке 3-простым графом.

Две вершины графа называются смежными, если существует соединяющее их ребро(дуга). Два ребра (дуги) смежны, если они имеют общую вершину.Если ребро (дуга) соединяет вершины, то говорят, что ребро (дуга) инцидентно вершинам, а вершины инцидентны ребру (дуге). Так, на рисунке 1 вершина X3 инциндентна ребрам U8, U9, U10. Смежными являются вершины X1 и X5, X3 и X4; ребра U5 и U6 являются смежными. рис.1 Неориентированный граф рис.2 Ориентированный граф рис.3 Смешанный граф 1.1 Способы задания графа Основными способами задания графа являются геометрический, аналитический и матричный.

Основой геометрического способа задания графа является рисунок, дающий изображение графа. Изображение графа в виде рисунка наглядно раскрывает содержательный смысл представляемого объекта. Рассмотрим аналитический способ задания графа.Говорят, что задан граф, если дано множество вершин Х, множество ребер U и инцидентор F, определяющий, какую пару вершин (хi,хj) Х соединяет ребро uk=(хi,хj). Матричный способ с помощью матрицы смежности и матрицы инцендентности.

Матрицей смежности неориентированного графа с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом: 1, если вершины хi и xj смежны; aij= 0, в противном случае; Для ориентированного графа: 1, если существует дуга <xi, xj>; aij= 0, в противном случае; Если в графе нет петель, то на главной диагонали в матрице смежности ставятся нули, в противном случае на главной диагонали – единица.

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