Лекции. Ескин В.И. Элементы теории графов. Материал предоставил В.Полунин (Элементы теории графов ОТКДС)

Посмотреть архив целиком

Элементы теории графов


Часто бывает полезно и наглядно изображать некоторую ситуацию в виде рисунка, состоящего из множества точек (вершин), представляющих собой основные элементы ситуаций и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графы. Язык и методы теории графов широко используются в качестве формальной модели для описания и исследования структурных свойств различных объектов, для решения задач, связанных с их (объектов) упорядочиванием.

В теории и практике АСУ, где требуется строить сложные управляющие системы, существует много задач, связанных с упорядочиванием их элементов. Это:

  • Календарное планирование (упорядочивание определенных работ по времени);

  • Сетевое планирование и управление;

  • Проектирование вычислительных сетей, систем связи и исследование на них проблем процессов передачи информации;

  • Выбор оптимальных маршрутов и потоков в транспортных сетях;

  • Построение переключательных схем, логических сетей;

  • Решение задач теории принятия решений.


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


Под графом будем понимать систему некоторых абстрактных объектов вместе с некоторыми парами из этих объектов, для которых заданы отношения связи между ними.

Иначе: граф – это геометрическая конфигурация, состоящая из множества точек и множества отрезков (кривых), соединяющих эти точки.

Граф G задается множеством точек или вершин X {x1,x2,…,xn} в n-мерном пространстве и множеством кривых (ребер) U {u1,u2,…,un}, соединяющих между собой все или часть точек, т.е. граф задается в виде G(X,U), где

X – множество вершин графа,

U – множество ребер графа.

Причем множество кривых (ребер) U удовлетворяет следующим условиям:

  1. Любая замкнутая кривая uU содержит только одну точку xX.


х


u


  1. Любая незамкнутая кривая содержит ровно две точки из множества X, которые являются ее граничными точками.


x1,x2X u



x1 x2





  1. Любые две кривые, принадлежащие множеству U, не имеют общих точек, за исключением точек из множества X.


x1 u1

x3


u2

x2


Если множество X конечно, то граф называется конечным графом.

Теория графов рассматривает только такие графы в которых координаты местоположения графов не играют роли и ребра графов могут быть любой формы.


x1 x2





x4 x3


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

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

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


u



x1 x2

исход (начало дуги) заход (конец дуги)


Замкнутое ребро называется петлей.


x1


u1




Если в графе есть как ориентированные, так и неориентированные ребра, то он называется смешанным графом.



На рисунке представлены ориентированный (а), неориентированный (б), смешанный (в) графы.


a) u3

x2 x3

u8

u1 u1


u10 x1 x4 u11



u5 u7


x5


б)

u2

x2 x3

u1 u7



u8 x1 x4 u9



u5 u6


x5


в) u2

x2 x3


u1 u6


u8 x1 x4 u9



u4 u7


x5

Здесь:

X={x1,x2,…x5} – вершины

В графе: а) {u1,u2,…u9} – дуги; {u10,u11} – петли

б) {u1,u2,…u7} – звенья; {u8,u9} – петли

в) {u1,u6} – звенья; {u2,u3,u4,u5,u7} – дуги; {u9,u10} – петли




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




u2

u3

u2 x2


u6



u7 x3

{u1,u2} – параллельные петли

{u5,u6} – параллельные дуги


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

Рассмотренный геометрический способ задания графа нагляден, но неудобен.


Аналитические способы задания графа


I. Ориентированный граф G есть совокупность двух объектов: множества вершин X и отображения F множества X на X, характеризующего связи между вершинами.

Обозначается G = (X,F).

Для X = {x1,x2,…,xn} отображение F задается под множествами FxiX, каждое из которых состоит из элементов xj, являющихся отображением элемента xi, т.е. множество Fxj указывает – к каким элементам множества X ведут дуги, исходящие из элемента xi (i = 1,..n).


Пример:

x1 x2


x4 x3


X={x1,x2,x3,x4,x5}

Fx1={x1,x2,x3,x4}

Fx2={x3}

Fx1={x2,x4}

Fx1=


II.Ориентированный граф есть совокупность множества вершин Х и множества ребер (дуг) U, являющегося подмножеством множества (XX) (декартово произведения множества Х само на себя).

Множество XX есть множество упорядоченных пар элементов (xi,xj) i,j=1..n. Поэтому задание множества ребер U их граничными точками xi,xj эквивалентно заданию некоторого бинарного отношения на множестве Х (отношение есть правило устанавливающее определенную связь между отдельными элементами некоторого множества).


Пример:


x1 x2


x4 x3

X={x1,x2,x3,x4}

U={(x1,x1), (x1,x2), (x1,x3), (x2,x3), (x3,x2), (x3,x4)}


Аналитические способы задания графа позволяют избавится от геометрических характеристик графа и расширяют возможности приложений теории графов с применением ЭВ Техники.

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

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


Матричные способы задания графов


I. Матрица смежности R ориентированного графа есть квадратная (nn) матрица R={rij} i,j=1..n, строки и столбцы которой соответствуют вершинам графа, а элементы матрицы rij – булевые переменные и равны соответственно

1, если xjFxi (т.е. есть дуга xi,xj)

ri,j=

0, если xjFxi (т.е. дуга xi,xj – отсутствует)


Матрица R полностью задает граф.


Пример:



x1 x2


x4 x3



1

1

1

1

0

0

1

0

0

1

0

1

0

0

0

0


R =


Для матрицы смежности


Si= ri,j= (j=1..n) число элементов множества Fxi , т.е. число элементов множества Х, в

которое исходит дуга из xi, (число дуг, исходящих из xi)

Pj= ri,j= (i=1..n) число дуг, которые заходят в вершину xj


Для неориентированного графа элементы матрицы смежности ri,j будут:

1, если есть ребро (звено) соединяющее xi с xj

ri,j=

0, если такое ребро отсутствует.


Матрица смежности для неографа будет симметричной (т.к. если есть xi,xj, то есть и xj,xi)


II. Матрица инциденций А для ориентированного графа G=(X,F) есть прямоугольная матрица A={aik}, строки которой поставлены в соответствие вершинам графа, а столбцы есть его ребра. Тогда элементы матрицы aik будут равны:

0 – если вершина xi не является граничной точкой для ребра uk

aik = 1 – если дуга uk заходит в вершину xi


Случайные файлы

Файл
24889-1.rtf
1.docx
17973-1.rtf
138536.rtf
fkontrol.doc




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.