Министерство  образования Российской Федерации

Поморский государственный университет им. М.В. Ломоносова

Математический  факультет

Кафедра алгебры и геометрии

 
 
 

  
 

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

Тема:

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

 
 
 
 
 

Выполнила студентка 

2 курса, 22 группы,

очного  отделения 
математического факультета

Елена Жильцова 
 

Научный руководитель

Кандидат  физико-математических наук, доцент кафедры  алгебры и геометрии

Зяблицева Л. В. 
 
 
 
 
 
 
 

Архангельск

2010

 

ОГЛАВЛЕНИЕ 

ВВЕДЕНИЕ          3

ГЛАВА I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ     4

1. Основные понятия       4
2. Способы задания графов      6

             1.2.1 Латинская матрица.       6

             1.2.2 Матрица смежностей.      7 

             1.2.3 Матрица инциденций.      11

       1.2.4 Матрицы связности и достижимости. Матрица

контрдостижимости.         13 

3. Метрические характеристики графа    15
4. Выявление маршрутов с заданным количеством рёбер 17
5. Определение экстремальных путей на графах. Метод

Шимбелла.           20

      1.6.  Нахождение кратчайших путей. Алгоритм Дейкстры. 22

      1.7 . Алгоритм нахождения максимального пути.   26

ГЛАВА II. ПРАКТИЧЕСКАЯ ЧАСТЬ      29 

ЗАКЛЮЧЕНИЕ          40

СПИСОК  ЛИТЕРАТУРЫ        41

 

ВВЕДЕНИЕ 

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

    В теоретико-множественной и геометрической формах определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, – любая матрица графа может быть введена в ЭВМ.

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

    Интерес к задачам маршрутизации объясняется  их использованием в качестве математических моделей многих проблем управления и автоматизации проектирования.

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

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

1. изучить основные матрицы графов и их теоремы;
2. научиться строить матрицы по графическому рисунку графа и графы по данной матрице;
3. изучить метрические характеристики графов, связанные с матрицами;
4. научиться находить пути графа по матрице (минимальные и максимальные).

 

    ГЛАВА I.  ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 

1.1 Основные понятия

    Пусть S – непустое множество, V⁽²⁾ – множество всех его двухэлементных подмножеств, U ϵ V⁽²⁾.

    Пара (S, U) называется неориентированным графом. Элементы множества S называются вершинами графа, а элементы множества U – рёбрами.

    Граф  G = (S, U) – это конечное множество вершин S и рёбер U.

    Если  в паре вершин x_i и x_j указано направление связи, то есть какая-то из вершин является первой, то соединяющий их отрезок u_k называется дугой, а вершины, определяющие дугу, называются концевыми вершинами.

    Если  концевые вершины совпадают, то дугу называют петлёй.

    В графе G могут существовать дуги (рёбра) о одинаковыми концевыми вершинами. Такие дуги называются параллельными.

    Если  в графе G = (S, U) все элементы множества U изображаются дугами, то граф называется ориентированным или орграфом, если рёбрами,  то неориентированным

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

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

    Граф  G называется, простым, если он не содержит петель и параллельных дуг.

    Типы  графов: • Мультиграф, в нём не допускаются петли, но пары вершин могут соединяться более чем одним ребром, эти рёбра называются кратными (рис.1).

• Псевдограф, в нём допускаются петли и кратные рёбра (рис.2).

      

          Рис. 1 Рис. 2

• Ориентированный граф, или орграф, состоит из конечного непустого множества V вершин и заданного набора Х упорядоченных пар различных вершин. Элементы из Х называются ориентированными рёбрами, или дугами. Нет петель и кратных дуг (рис. 3).

    

    

     Рис. 3 Рис. 4

• Направленный граф – это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).
• Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.

    Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер u₀, x₁, u₁, … u_n-1, x_n, u_n; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним.

    Маршрут называется замкнутым, если u₀  =  u_n, и открыт в противном случае.

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

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

    Цикл (контур), в котором все вершины  попарно различны, называется простым.

    Длина маршрута равна n, то есть количеству рёбер в нём.

    Расстоянием d(u, v) между двумя вершинами u и v графа G называется длина кратчайшей простой цепи, соединяющей их; если u и v не соединены, то полагаем что

d(u, v) = ∞.

    Графы, для которых сохраняется отношение  инцидентности, называются изоморфными.

    Если  в орграфе существует маршрут, связывающий  вершины x_i и x_j, то говорят, что вершина x_j достижима из вершины x_i. Любая вершина считается достижимой из себя самой. Вершина орграфа называется источником, если из нее достижима любая вершина орграфа.

    Орграф  называется сильно связным, если любые две его вершины сильно связаны. Две вершины x_i и x_j любого графа сильно связаны, если существует ориентированный путь из x_i в x_j и ориентированный путь из x_j в x_i. Сильно связными компонентами орграфа называются его максимально сильно связные подграфы. 
 
 
 
 
 

2. Способы задания графа

 

1. Латинская матрица

 

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

     Рис. 1.1 

 

     Таблица 1.1.

    Если  граф неориентированный, то в латинской  матрице просто штрихуют соответствующую  клеточку в таблице.  

      
 
 
 

2. Матрица смежностей

 

    Наиболее  часто граф задают с помощью матриц смежности и инциденций.

    Матрицей  смежностей А = ||а_ij|| помеченного графа G с p вершинами называется (p_˟p)-матрица, в которой а_ij = 1, если вершина u_i смежна с u_j, и а_ij = 0 в противном случае. Строки и столбцы этой матрицы соответствуют вершинам графа, а её (ij) –элемент равен числу кратных рёбер, связывающих вершины v_i и v_j (или направленных от вершины v_i к вершине v_j для орграфа).

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

       

 
 
 
 
 
 
 
 
 

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

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

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

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

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

 
 
 
 
 
 

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

    Доказательство: Рассмотрим два графа G₁ и G₂, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их смежность: вершины x₁ и x₂ тогда и только тогда смежны в G, когда их образы y₁ = s(x₁) и y₂ = s(x₂) смежны в G₁. Тогда, если P(G) = P и P(G₁) = P⁽¹⁾, то p_s(i)s(j)=p_ij, i, j = (1, n).

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

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

      

                                  Рис. 1.3

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

    Р₁= Р₂= Р₃= 
 
 

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

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

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

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

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

      
 
 
 
 
 
 

                                        Рис. 1.4

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

      
 
 
 
 
 
 
 
 
 

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

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

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

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

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

 

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

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

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

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

      
 
 

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

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

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

    Доказательство:  Рассмотрим два графа G₁ и G₂, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их инцидентность: вершины x₁ и x₂ тогда и только тогда инцидентны в G, когда их образы y₁ = s(x₁) и y₂ = s(x₂) инцидентны в G₁. Тогда, если P(G) = P и P(G₁) = P⁽¹⁾, то p_s(i)s(j)=p_ij, i, j = (1, n).

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

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

     Рис. 1.5 
 

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

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 

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

     

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

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

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

        
 
 

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

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

      

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

     Рис. 1.6

       
 

     С =  L =  

     

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

1. x_i;
2. x₂, x₃, x₄;
3. x₅, x₆.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 

     Рассмотрим  связный граф G = (S, U), пусть x₁ и x₂ – две его вершины. Длина кратчайшего (x₁, x₂)-маршрута называется расстоянием между вершинами x₁ и x₂, обозначается через d(x₁ , x₂). Очевидно, что расстояние между вершинами является простой цепью и d(x₁ , x₂)=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 и x₁, x₂, …, x_d+1 – одна из диаметральных цепей графа G. Рассмотрим матрицу смежности вершин P(G) и выберем нумерацию вершин так, чтобы вершины x₁, x₂, …, x_d+1 имели номера 1, 2, … , d+1 соответственно. Так как цепь x₁, x₂, …, x_d+1 является подграфом G′ ᴄ G, то P(G) =( )представляет собой клеточную матрицу, в левом верхнем углу которой из-за выбранной нумерации вершин расположена матрица смежности подграфа G′. Этот подграф – простая цепь, т. е.