Учебное пособие для студентов всех специальностей Саратов 2009 Все права на размножение и распространение в любой форме остаются за разработчиком



страница1/3
Дата28.12.2017
Размер0.5 Mb.
#5531
ТипУчебное пособие
  1   2   3


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

Федеральное агентство по образованию



Саратовский государственный технический университет

А.В.СЕРЕБРЯКОВ


ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

Учебное пособие

для студентов всех специальностей

Саратов 2009

Все права на размножение и распространение в любой форме остаются за разработчиком.

Нелегальное копирование и использование данного продукта запрещено.

Составители: Серебряков Андрей Владимирович

Рецензенты

Кафедра информационных систем и технологий

Поволжского кооперативного института МУПК;

доктор технических наук, профессор Д.В.Сперанский


410054, Саратов, ул. Политехническая, 77

Научно-техническая библиотека СГТУ

тел. 52-63-81, 52-56-01

http://lib.sstu.ru
Регистрационный номер

© Саратовский государственный

технический университет, 2009


ВВЕДЕНИЕ
Теория графов представляет собой область дискретной математики, для которой характерным является геометрический подход к изучению объектов. Зародилась теория графов в 1736 г., когда Л.Эйлер решил популярную математическую головоломку о кенигсбергских мостах и получил критерий существования обхода всех ребер графа без повторений. В 1847 г. Г.Кирхгоф разработал теорию деревьев (графов специального вида) для исследования электрических цепей. Независимо от этого теория деревьев возникла в 1857 г. в работах А.Кэли, посвященных подсчету числа изомеров предельных углеводородов.

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

Широкое применение теории графов для решения прикладных задач потребовало включения этого раздела в образовательные стандарты по математике для инженерных специальностей и разработки соответствующего методического обеспечения. Настоящее учебное пособие содержит начальные сведения из теории графов. Рассмотрены задачи о минимальном остовном дереве и кратчайших путях на графе. Приведен также список рекомендованной литературы, который охватывает общие вопросы теории графов и ее приложения. Этот список содержит широко известные монографии и учебники прошлых лет издания [1-5], а также новые учебники и учебные пособия [6-10].

1. НАЧАЛЬНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ


    1. Определения графа и ориентированного графа


Граф G - совокупность двух конечных множеств G={V,E}, таких, что VØ и множество E состоит из неупорядоченных пар элементов множества V. Элементы множества V называются вершинами графа G, элементы множества E - ребрами. Граф G называют еще неориентированным графом. Для графа с m вершинами и n ребрами используется название (m,n)-граф.

Вершины графа vi и vj называются смежными, если e={vi,vj}E. Ребро e в этом случае называется инцидентным вершинам vi и vj.

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

Пример 1. Рассмотрим граф G={V,E}, где V={v1,…,v6} и E={{v1,v2},{v1,v4},{v1,v6},{v2,v3},{v2,v4},{v2,v6},{v4,v6},{v5,v6}}. На рис.1 представлена одна из возможных диаграмм данного графа.


v2



v1

v2

v1

v3

v3

v6



v4

v4

v6

v5



v5

Рис.2

Рис.1

На этой диаграмме возникла точка, которая лежит на пересечении линий, изображающих ребра, но не является вершиной графа. На рис.2 представлена другая диаграмма графа G, которая не содержит таких точек. ■

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

Пусть V={G,A}, где множество А состоит из упорядоченных пар вершин. Тогда совокупность {G,A} задает ориентированный граф (орграф). Элементы множества А называют в этом случае дугами орграфа. Если существует a=(vi,vj)A, то вершины vi и vj орграфа называют смежными. Эти вершины инцидентны с дугой а. Вершина vi называется началом дуги а, вершина vj - концом. На диаграмме дуги изображаются линиями со стрелками, чтобы различать начало и конец дуги.



Пример 2. На рис.3 изображены диаграммы двух ориентированных графов G1={V,A1} и G2={V,A2}. Здесь V={v1,…,v4}, A1={(v1,v2),(v1,v3),(v2,v4)} и A2={(v1,v2),(v3,v1),(v4,v2)}. Заметим, что A1≠A2. ■

Рис.3


Любой неориентированный граф можно представить в виде ориентированного графа с тем же множеством вершин. Для этого каждое ребро {vi,vj} неориентированного графа нужно заменить парой дуг (vi,vj) и (vj,vi).

В
v1



v2

u2

u1

G

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


Рис.4. G - мультиграф; H - псевдограф


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








H


Рис.5. G - орграф с кратными дугами; H - орграф без кратных дуг

G

Существует взаимно однозначное соответствие между ориентированными графами с множеством вершин V без кратных дуг и бинарными отношениями на множестве V. Действительно, для данного множества вершин V орграф полностью определяется заданием множества дуг AV2. Бинарное отношение на множестве V также определяется заданием подмножества  декартова квадрата V2. Орграф {V,A} и бинарное отношение на множестве V соответствуют друг другу, если =A. Отношения, соответствующие неориентированным графам, обладают свойством симметричности.


    1. Задание графов с помощью матриц

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

Граф можно задать матрицей смежности, которая представляет собой квадратную матрицу порядка m, где m - число вершин графа. Элементы матрицы смежности pij (i,j=1,…m) определяются по следующему правилу:



. (1)

Рассматривая в выражении (1) упорядоченные пары вершин (vi,vj), получим правило для определения элементов матрицы смежности орграфа.



Пример 3. Рассмотрим граф G на рис.1. Следуя правилу (1), составим для G матрицу смежности










0

1

0

1

0

1
















1

0

1

1

0

1







[pij]

=




0

1

0

0

0

0
















1

1

0

0

0

1
















0

0

0

0

0

1
















1

1

0

1

1

0




. ■

Заметим, что получилась симметричная матрица. Матрица смежности будет симметричной для любого неориентированного графа.

Пример 4. Рассмотрим ориентированный граф G1 на рис.3. Для данного орграфа матрица смежности принимает вид










0

1

1

0
















0

0

0

1







[pij]

=




0

0

0

0
















0

0

0

0




. ■

В качестве самостоятельного упражнения предлагается составить матрицу смежности для орграфа G2, изображенного на рис.3.

Любой (m,n)-граф может быть задан матрицей инцидентности с элементами rij (i=1,…,m; j=1,…,n), которые определяются по следующему правилу:



(2)

Для орграфа правило (2) принимает вид



(3)

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






e1



1

0

0

0

0

0

0

0





e3



1

1

1

0

0

0

0

0







0

0

1

0

0

0

0

0





e2

v3



0

1

0

1

1

1

0

0





v1



0

0

0

1

0

0

1

0





v4



0

0

0

0

0

1

0

1





e6

e4



0

0

0

0

1

0

1

1





v5

e5

v6

e7

e8

v7

Рис.6




Пример 6. Для орграфа, изображенного на рис.7, матрица инцидентности имеет вид:





-1

0

0

1







1

0

1

0







0

1

-1

0







0

-1

0

-1






Задав граф с помощью матрицы смежности, мы можем по элементам этой матрицы определить степени вершин графа.



Степенью вершины deg(v) в графе G называется число ребер, инцидентных вершине v. Для вершины орграфа deg(v)=od(v)+id(v), где полустепень исхода od(v) - число дуг, начинающихся (исходящих) из v, и полустепень захода id(v) - число дуг, заканчивающихся (заходящих) в v. Нетрудно убедиться, что имеют место равенства

m

deg(vi)=pij (4)



j=1

и



m m

od(vi)= pij, id(vi) = pki, (5)



j=1 k=1

которые позволяют вычислять степени вершин через элементы матрицы смежности.


Пример 7. Возьмем матрицу смежности графа из примера 3 и вычислим по формуле (4) степени всех вершин. Получим следующие значения:
deg(v1)=3; deg(v2)=4; deg(v3)=1; deg(v4)=3; deg(v5)=1; deg(v6)=4.
Те же значения получаются в результате непосредственного подсчета числа инцидентных ребер для каждой вершины графа на рис.1. ■
Вершины, у которых deg(v)=1, называют висячими (концевыми) вершинами. Ребро, инцидентное концевой вершине, также называется концевым. В предыдущем примере концевыми вершинами оказались v3 и v5, концевыми ребрами - {v2,v3} и {v5,v6}. Если в графе имеется вершина, у которой deg(v)=0, то она называется изолированной.

С понятием степени вершины связан первый результат, полученный Л.Эйлером (L.Euler) в теории графов.


Теорема 1. Сумма степеней всех вершин графа есть четное число, равное удвоенному числу его ребер.
▲ Действительно, каждое ребро инцидентно двум вершинам графа, в сумму степеней вершин оно вносит 2. Значит,

m

 deg(vi)=2n,



i=1

где m, n - соответственно число вершин и ребер графа. ▲


В качестве самостоятельного упражнения предлагается доказать следствие из теоремы 1:

В любом графе число вершин нечетной степени четно.


    1. Изоморфизм графов

Пусть даны графы G={VG,EG} и H={VH,EH}. Если между множествами вершин VG и VH существует взаимно однозначное соответствие, сохраняющее смежность, то графы G и H изоморфны. Изоморфные графы можно изобразить одной и той же диаграммой. Изоморфизм графов есть отношение эквивалентности, которое разбивает множество всех графов на непересекающиеся подмножества - классы эквивалентности.

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











0

0

1

0













0

0

1

1




A

=




1

1

0

1













0

1

1

0



Введем в рассмотрение граф H с множеством вершин {v1,…v4}, изоморфный G. Для этого установим взаимно однозначное соответствие между вершинами u1v2, u2v4, u3v1, u4v3, сохраняя смежность. Диаграмма графа H приведена на рис.8б.


v4

v2

u2

u1


Рис.8

v3

u3

u4

(a)

(б)

v1

Матрица смежности графа H имеет вид:












0

1

1

1













1

0

0

0




B

=




1

0

0

1













1

0

1

0




Матрицы A и B имеют один и тот же порядок m=4.

Чтобы установить связь между элементами матриц A и B, представим соответствие между множествами вершин U и V в виде , где s(1)=2, s(2)=4, s(3)=1, s(4)=3.

Тогда имеют место равенства

Bs(i)s(j)=Aij (i,j=1,…m) (6)

Определим матрицу S порядка m с элементами


Для данных графов G и H матрица S имеет вид











0

0

1

0













1

0

0

0




S

=




0

0

0

1













0

1

0

0




Путем непосредственных вычислений проверяется справедливость матричного равенства

B=SAS-1,

равносильного равенствам (6). ■

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



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

Утверждение теоремы 2 верно также для мульти- и псевдографов, ориентированных графов.



    1. Каталог: new -> SubjectFGOS
      SubjectFGOS -> Лекция №6 экологические принципы рационального использования природных ресурсов и охраны природы. Основы экономики природопользования
      SubjectFGOS -> Методические указания к практическим занятиям и самостоятельной работе студентов по курсу математики для студентов всех специальностей
      SubjectFGOS -> Основы порошковой металлургии
      SubjectFGOS -> 10. Особо опасные экотоксиканты
      SubjectFGOS -> Окислительно-восстановительные реакции
      SubjectFGOS -> Вопросы для подготовки к экзамену по информатике
      SubjectFGOS -> Лекция №8 Метаболизм микроорганизмов План лекции: Обмен веществ как совокупность реакций катаболизма и анаболизма
      SubjectFGOS -> Методические указания к выполнению лабораторной работы по дисциплине «Информатика» студентами направления 080500. 62 «Менеджмент»
      SubjectFGOS -> Информационные технологии в управлении
      SubjectFGOS -> Методические указания к выполнению лабораторной работы по курсу "Основы технологии производства и ремонта автомобилей" для студентов специальности


      Поделитесь с Вашими друзьями:
  1   2   3




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница