Матрицы в теории графов

Автор: Пользователь скрыл имя, 07 Декабря 2011 в 21:38, курсовая работа

Краткое описание

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

Оглавление

ВВЕДЕНИЕ 3
ГЛАВА I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 4
Основные понятия 4
Способы задания графов 6
1.2.1 Латинская матрица. 6
1.2.2 Матрица смежностей. 7
1.2.3 Матрица инциденций. 11
1.2.4 Матрицы связности и достижимости. Матрица
контрдостижимости. 13
Метрические характеристики графа 15
Выявление маршрутов с заданным количеством рёбер 17
Определение экстремальных путей на графах. Метод
Шимбелла. 20
1.6. Нахождение кратчайших путей. Алгоритм Дейкстры. 22
1.7 . Алгоритм нахождения максимального пути. 26
ГЛАВА II. ПРАКТИЧЕСКАЯ ЧАСТЬ 29
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 41

Файлы: 1 файл

Матрицы в теории графов.doc

— 1.13 Мб (Скачать)

    Таким образом, существует взаимно однозначное соответствие между помеченными графами с p вершинами и симметрическими бинарными (p˟p)-матрицами с нулями на диагонали. На рисунке 1.2 показаны помеченный граф G и его матрица смежностей А. Легко заметить, что суммы элементов матрицы А по строкам равны степеням вершин графа G.

       

 
 
 
 
 
 
 
 
 

      Рис. 1. 2. Помеченный граф и его матрица смежностей. 

    Матрица смежности неориентированного графа всегда симметрична, а орграфа – в общем случае несимметрична. Неориентированным рёбрам соответствуют пары ненулевых элементов, симметричных относительно главной диагонали матрицы, дугам – ненулевые элементы матрицы, а петлям – ненулевые элементы главной диагонали. В столбцах и строках, соответствующих изолированным вершинам, все элементы равны нулю. Элементы матрицы простого графа равны 0 или 1, причём все элементы главной диагонали нулевые.

    Элементы  матрицы определяются следующим  образом: 

          для неориентированного графа:

      
 для ориентированного графа:

 
 
 
 
 
 

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

    Доказательство: Рассмотрим два графа G1 и G2, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их смежность: вершины x1 и x2 тогда и только тогда смежны в G, когда их образы y1 = s(x1) и y2 = s(x2) смежны в G1. Тогда, если P(G) = P и P(G1) = P(1), то ps(i)s(j)=pij, i, j = (1, n).

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

     Пример 1. Доказать, что графы изоморфны (рис. 1.3).

      

                                  Рис. 1.3

     Решение: воспользуемся теоремой и проанализируем матрицы смежности данных графов.  

    Р1= Р2= Р3= 
 
 

    Видно, что Р2= Р3. Если одновременно переставить в Р2 вторую и пятую строки и второй и пятый столбец, то получится матрица Р1. Следовательно, по теореме все три указанных графа изоморфны. 

      Из доказанной теоремы следует, что ранги матриц смежности изоморфных графов совпадают. Это позволяет ввести для графа следующее определение ранга: рангом графа называется ранг его матрицы смежности. Обозначается ранг графа – rankG,

    В Примере 1   rankР1 = 2,  следовательно, rankG1 = 2.

    Аналогично  можно определить и матрицу смежности  дуг. Это так же квадратная матрица m˟m порядка, где m – число дуг.

    Пример 2. Рассмотрим следующий граф (рис. 1.4):

      
 
 
 
 
 
 

                                        Рис. 1.4

    Элементы  qij матрицы смежности дуг равны единице, если дуга ui непосредственно предшествует дуге uj, и равны нулю в остальных случаях. Для неориентированного графа элемент qij равен единице, если ui и uj смежны, и нулю в остальных случаях.

      
 
 
 
 
 
 
 
 
 

    Утверждение: Для того, чтобы n-вершинный граф G с матрицей смежности A = A (G) имел хотя бы один контур, необходимо  и достаточно, чтобы матрица K = A2 + A3 +…+An имела ненулевые диагональные элементы.

    Доказательство:

    Достаточность: Пусть K = [kij] и для некоторого номера i выполняется kij>0. в этом случае для некоторого r из {2, …, n} справедливо a(r)ii>0, а следовательно найдётся путь в G из xi в xi. Но тогда в силу того, что в графе G из всякого цикла можно выделить простой цикл, в орграфе G найдётся простой контур.

    Необходимость: Пусть в графе G имеется некоторый контур.  Так как из всякого контура можно выделить простой контур, нетрудно увидеть, что длина простого контура не превышает числа вершин n. Но тогда в силу того,  что элемент матрицы ориентированного графа равен числу всех путей длины l, то для любой вершины xi, принадлежащей некоторому простому контуру длины l, где 2 ≤ l ≤ n, элемент a(l)ii матрицы Al отличен от нуля, а следовательно, и элемент kii матрицы К отличен от нуля.  

    Простой взвешенный граф так же может быть представлен своей матрицей весов = (ωij), где ωij – вес ребра, соединяющего вершины xi и xj. Веса несуществующих рёбер полагают равными нулю или бесконечности в зависимости от приложений. Очевидно, что матрица весов является простым обобщением матрицы смежности вершин. 
 
 

 

1.  2.  3 Матрица инциденций 

    Другой  матрицей, связанной с графом G, в котором помечены и вершины и рёбра, является матрица инциденций B = |bij|. В этой (pxq)-матрице bij = 1, если vi и xj инцидентны, и bij = 0 а противном случае. Как и матрица смежностей, матрица инциденций определяет граф G с точностью до изоморфизма. На самом деле уже любые p-1 строки матрицы B определяют G, поскольку каждая строка равна сумме по модулю 2 всех остальных строк.

    Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-ый элемент равен 1, если вершина vi инцидентна ребру хj,и равен нулю, если vi и хj не инцидентны.  

    Для неориентированного графа элементы данной матрицы задаются следующим образом:

      
 
 

     Для ориентированного графа элементы матрицы задаются так:

     Строки  матрицы инциденций называют векторами инциденций графа G. Матрица инциденций также однозначно определяет структуру графа. Для матрицы инциденций справедлива теорема, аналогичная для матрицы смежности. 

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

    Доказательство:  Рассмотрим два графа G1 и G2, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их инцидентность: вершины x1 и x2 тогда и только тогда инцидентны в G, когда их образы y1 = s(x1) и y2 = s(x2) инцидентны в G1. Тогда, если P(G) = P и P(G1) = P(1), то ps(i)s(j)=pij, i, j = (1, n).

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

      Пример 3: Рассмотрим граф (Рис. 1.5) 
 
 
 
 
 
 

     Рис. 1.5 
 

     Его матрица инциденций имеет вид:

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  1. 2.  4 Матрицы связности и достижимости. Матрица контрдостижимости
 

     Определим матрицы связности и достижимости. Пусть P(G) – матрица смежности вершин графа G = (Sn, U), а B = E + P + P2 + … + Pn. Введём матрицу C = (cij), i,j = (1, n) по правилу:

     

     Матрица С называется матрицей связности, если G – неориентированный граф, и матрицей достижимости, если G – ориентированный. Это значит, что в графе G тогда и только тогда существует маршрут из вершины xi в xj, когда cij = 1.

     Таким образом, в матрице С содержится информация о существовании связей между различными элементами графа G  посредством маршрутов.

     Матрица контрдостижимости L = (lij), i, j = (1, n), определяется следующим образом:

        
 
 

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

     Пусть F = C*L, где операция * означает поэлементное произведение матриц С и L: fij = cij lij. Элемент fij матрицы F равен единице тогда и только тогда, когда вершины xi и xj взаимно достижимы, т. е. xi достижима из xj, а xj – из xi. Таким образом, сильная компонента орграфа, содержащая вершину xi, состоит из элементов xj, для которых fij = 1.

      

      Пример 4: Матрицы достижимости С и контрдостижимости L для данного графа равны 
 
 
 
 
 

                 Рис. 1.6

       
 

     С =  L =  

     

     По  матрице F легко определить состав вершин трёх подграфов, образующих сильно связанные компоненты исходного графа:

  1. xi;
  2. x2, x3, x4;
  3. x5, x6.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    1. 3 Метрические характеристики графа
 

     Рассмотрим  связный граф G = (S, U), пусть x1 и x2 – две его вершины. Длина кратчайшего (x1, x2)-маршрута называется расстоянием между вершинами x1 и x2, обозначается через d(x1 , x2). Очевидно, что расстояние между вершинами является простой цепью и d(x1 , x2)=0. Для любой вершины x величина e(x) = max d(x, y) называется эксцентриситетом вершины x. Максимальный из всех эксцентриситетов называется диаметром графа и обозначается d(G), т. е. d(G) = max e(x) = max max d(x, y).

     Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через r(G): r(G) = min e(x) = min max d(x, y).

     Вершина x называется периферийной, если её эксцентриситет равен диаметру графа, т. е. e(x) = d(G). Простая цепь, расстояние между концами которой равно d(G), называется диаметральной цепью. 

     Теорема: Для любого связного графа G справедливо неравенство d(G) ≤ rankG.

     Доказательство: Пусть d(G) = d и x1, x2, …, xd+1 – одна из диаметральных цепей графа G. Рассмотрим матрицу смежности вершин P(G) и выберем нумерацию вершин так, чтобы вершины x1, x2, …, xd+1 имели номера 1, 2, … , d+1 соответственно. Так как цепь x1, x2, …, xd+1 является подграфом G′G, то P(G) =( )представляет собой клеточную матрицу, в левом верхнем углу которой из-за выбранной нумерации вершин расположена матрица смежности подграфа G′. Этот подграф – простая цепь, т. е.

Информация о работе Матрицы в теории графов