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

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

2

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ РОСИЙСКОЙ ФЕДЕРАЦИИ

Государственное Образовательное Учреждение Высшего Профессионального Образования «Воронежский Государственный Технический Университет» (ГОУВПО «ВГТУ»)

Кафедра: Высшей математики и физико-математического моделирования

КУРСОВАЯ РАБОТА

по дисциплине «Математика»

«Метрические характеристики графа»

Выполнил: студент группы

РК-051 Жищенко С.А.

Руководитель: Ускова Н.Б.

Оценка:

Дата защиты:

Воронеж 2006 г.

Содержание

• ПОНЯТИЕ "ГРАФ" 3
• МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ГРАФОВ 7
• ОПЕРАЦИИ НАД ГРАФАМИ 9
• МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ 10
• МЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИ ГРАФА 13
• ПРИЛОЖЕНИЕ ТЕОРИИ ГРАФОВ В РАЗЛИЧНЫХ ОБЛАСТЯХ НАУКИ И ТЕХНИКИ. 15
• ПРАКТИЧЕСКАЯ ЧАСТЬ 17
• ЛИСТИНГ ПРОГРАММЫ 20

ПОНЯТИЕ "ГРАФ"

Пусть V - непустое множество, V(2) - множество всех его двухэлементных подмножеств. Пара (V,E), где E - произвольное подмножество множества V(2), называется графом (неориентированным графом). Элементы множества V называются вершинами графа, а элементы множества E - ребрами. Итак, граф - это конечное множество V вершин и множество E ребер, E?V(2).

Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в).

Множества вершин и ребер графа G обозначается соответственно VG и EG. Вершины и ребра графа называются его элементами. Число |VG| вершин графа G называется его порядком и обозначается |G|.

Если |G|=n,|EG|=m, то граф называют (n, m) - графом.

Говорят, что две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если e={u, v}- ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v.

Два ребра называются смежными, если они имеют общий конец.

Вершина v и ребро e называются инцидентными, если v является одним из концов ребра e, и не инцидентными в противном случае.

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

Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается NG(v) или просто N(v).

Графы удобно изображать в виде рисунков (геометрических графов). Геометрический граф в пространстве n-мерном евклидовом пространстве еn есть множество точек пространства еn и множество E простых кривых, таких: 1) что каждая замкнутая кривая в E содержит только одну точку v множества V; 2) каждая незамкнутая кривая в E содержит ровно две точки множества V, которые являются ее граничными точками; 3) кривые в E не имеют общих точек кроме точек из множества V. При этом точки множества V соответствуют вершинам графа, а соединяющие пары точек линии - ребрам.

Граф G называется полным, если любые две его вершины смежны. Полный граф порядка n обозначается Kn.

Граф называется вырожденным (пустым), если любые две его вершины не смежны (т.е. у него нет ребер).

Пусть G и H графы, а ?: VG>VH - биекция. Если для любых вершин u и v их образы ?(u) и ?(v) смежны в H тогда и только тогда, когда u и v смежны в G, то эта биекция называется изоморфизмом графов G и H, асами графы G и H - изоморфными. Изоморфные графы будем обозначать G?H (атакже HG).

Если граф G изоморфен геометрическому графу G', то G' называется геометрической реализацией графа G.

Очевидно, что отношение изоморфизма графов является эквивалентностью. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т.е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой элементов, но именно это игнорируется при введении понятия "граф".

В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие "помеченного графа". Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки, например 1, 2,..., n. Отождествив каждую из вершин графа с ее номером (и, следовательно, множество вершин - с множеством чисел {1, 2,..., n }), определим равенство помеченных графов G и H одного и того же порядка: G=H тогда и только тогда, когда EG =EH.

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

Иногда рассмотренное выше понятие "граф" оказывается недостаточным и приходится рассматривать более общие объекты, в которых две вершины могут соединяться более чем одним ребром. Так возникает понятие "мультиграф". Мультиграф - это пара (V, E), где V- непустое множество (вершин), а E- семейство подмножеств множества V(2) (ребер). Употребление термина "семейство" вместо "множество" означает, что элементы множества V(2) могут в E повторяться, т.е. допускаются кратные ребра.

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

Изучаются также ориентированные графы. Тогда множество V(2) заменяется декартовым квадратом V2, состоящим из упорядоченных пар элементов множества V. Ориентированный граф (или орграф) - это пара (V, A), где V- множество вершин, A- множество ориентированных ребер, которые называются дугами, AV2.

Если a=(v1, v2) - дуга, то вершины v1 и v2 называются ее началом и концом соответственно.

Аналогично неориентированному определяется ориентированный мультиграф. Рассматриваются также смешанные графы, у которых есть и дуги, инеориентированные ребра. Заменяя каждую пару (u, v) из множества E, ориентированного (или смешанного) графа G неупорядоченной парой {u, v}, состоящей из тех же элементов uи v, получаем ассоциированный с G=(V, E) графом псевдограф H=(V, E0). Также говорят, что граф H есть основание графа G.

Орграф называется турниром, если его основание является полным графом.

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

Рис.3. Граф Петерсена

Пусть G - граф, w: EG>R+ вещественнозначная функция, ставящая в соответствие каждому ребру e неотрицательное число w(e) - вес ребра e. Пару (G, w) назовем взвешенным графом. Под весом любого подграфа (возможно, несобственного) взвешенного графа будем понимать сумму весов его ребер.

МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ГРАФОВ

Пусть G -помеченный граф порядка n, VG={1, 2,..., n}. Определим бинарную nЧn-матрицу A=A(G), положив

A(G) называется матрицей смежности графа G. Это симметричная матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.

Очевидно, что соответствие G>A(G) определяет биекцию множества помеченных графов порядка n на множество бинарных симметричных nЧn-матриц с нулевой диагональю.

Аналогично определяются матрицы смежности A мульти - и псевдографов: ik равно числу ребер, соединяющих вершины i и k (при этом петля означает два ребра).

Также определяется матрица смежности A(G) ориентированного графа.

Очевидно, что если A(G) - матрица смежности орграфа G порядка n, то

т.е. число единиц в i-й строке матрицы A(G) равно полустепени исхода i-й вершины, а число единиц в k-м столбце равно полустепени захода k-й вершины.

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

Теорема верна также для мультиграфов, псевдографов и орграфов.

Пусть G -(n, m) - граф, VG={1, 2,..., n} EG={e1, e2,..., em}. Определим бинарную nЧm-матрицу I=I(G) условиями

Матрица I называется матрицей инцидентности графа G. В каждом ее столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G>I(G) является биекцией множества помеченных (n, m) - графов с занумерованными ребрами на множество nЧm-матриц, удовлетворяющих описанным условиям.

Матрица инцидентности I для орграфа:

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

Теорема верна также для мультиграфов, псевдографов и орграфов.

Свойства матриц смежности и инцидентности:

1) Сумма элементов матрицы A(G), где G=(V, E) - мультиграф, V={v1, v2,..., vn}, по i-йстроке (или по i-му...