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

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

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

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

 
 
 

  
 

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

Тема:

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

 
 
 
 
 

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

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 для орграфа).