Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты



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


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

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

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

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

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



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

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

Саратов 2009

УДК 519.17

ББК 22.174

С 32
Рецензенты:

Кафедра теории функций и приближений

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

им. Н.Г.Чернышевского

Доктор физико-математических наук, профессор

В.Ю.Ольшанский

Одобрено

редакционно-издательским советом

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

Серебряков А.В.

С32 Ведение в теорию графов: учеб. пособие. Саратов: Сарат. гос. техн. ун-т, 2009. 36с.

ISBN 978-5-7433-2082-0

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

Предназначается для студентов всех специальностей технического университета, изучающих курс математики
УДК 519.17

ББК 22.174

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

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

ISBN 978-5-7433-2082-0 © Серебряков А.В., 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   2   3   4

Похожие:

Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 Ббк 22. 12 С 32 Рецензенты
С 32 Элементарный курс математической логики. Логические функции: учеб пособие. Саратов: Сарат гос техн ун-т, 2011. 32 с
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60
Калинина В. Н., Соловьев В. И. Введение в многомерный статистический анализ: Учебное пособие / гуу. – М., 2003. – 92 с
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие Москва, 2009 удк 811. 111 Ббк 81. 2Англ к 893 к 893
Учебное пособие предназначено для студентов продвинутого этапа обучения гуманитарных специальностей. Пособие базируется на оригинальном...
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие Москва 2002 ббк 63. 3 /2/ я 73 Рецензент: Иванова А. А
Учебное пособие предназначено для студентов I курса всех направлений и всех специальностей дневной формы обучения
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconКонспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32
Учебное пособие предназначено для студентов факультета Кибернетики, изучающих на пятом семестре математическую лингвистику и основы...
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие для самостоятельной работы обучающихся Сызрань 2007 Составители: П. П. Гавриш, Ю. А. Мелешкин удк 621. 375 Ббк 32. 85
Учебное пособие предназначено для обучающихся всех специальностей, изучающих теорию электрических цепей
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие Оренбург, 2007 удк 811. 131. 1(075) ббк 81. 2Фр-923 а 23 Рецензенты
Данное учебное пособие предназначено для студентов, занимающихся изучением древних языков и античной культуры и имеет целью помочь...
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие Омск Издательство Омгту 2009 удк 55 (075) ббк 26. 3я73 Б44 Рецензенты
Охватывает большие территории и многокилометровые толщи пород
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие Уфа 2006 удк 519. 8 Б 19 ббк 22. 1: 22. 18 (Я7)
Бакусова С. М. Математика. Часть Математическое программирование / Учебное пособие. Уфа: ООО полиграфстудия «Оптима», 2006. – 71...
Учебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты iconУчебное пособие по физико-химическим методам анализа и электрохимии для студентов специальностей 240502. 65, 240302. 65, 550800
Г. П. Денисова, А. В. Денисов, С. С. Попова. Саратов: Сарат гос техн ун-т, 2009. 52 с
Разместите кнопку на своём сайте:
ru.convdocs.org


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