ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5093
Скачиваний: 30
26
Тема
1.
ОСНОВНЫЕ
ПОНЯТИЯ
И
ОПРЕДЕЛЕНИЯ
ТЕОРИИ
ГРАФОВ
1.1
Определение
графа
Теория графов оперирует формальными моделями объек-
тов, имеет дело со свойствами самих графов независимо от того,
какова природа объектов, описываемых графами. Использова-
ние аппарата теории графов для разработки алгоритмов конст-
рукторского и технологического проектирования схем ЭВА
приводит к повышению эффективности и качества создаваемых
объектов.
Понятие графа опирается на понятие множества. Графом
можно назвать объект, состоящий из двух множеств: множества
точек и множества линий. Множество точек графа обозначается
X={x
1
,x
2
,…,x
n
} и называется множеством вершин. Суммарное
число n всех вершин графа называется мощностью множества
X
графа и обозначается |X|=n.
Множество линий, соединяющих любые пары вершин
(x
i
, x
j
), принадлежащих множеству X, называется множеством
ребер или дуг и обозначается:
U={u
1
, u
2
,…,u
m
}, где u
i
– ребро графа.
Суммарное число m всех рёбер графа называется мощно-
стью множества рёбер графа и обозначается |U|=m.
Таким образом, графом можно считать математический
объект, который обозначается G=(X,U) и состоит из множества
вершин Х и множества ребер U, находящихся между собой в
некотором отношении.
В общем случае множество U можно представить в виде
∪
∪
→
−
=
U
U
U
U
o
.
U – подмножество неориентированных линий, для которых
не существенен порядок соединения вершин. Подмножество U
называется подмножеством ребер. Причем каждое ребро
27
u
i
∈U определяется неупорядоченной парой вершин x, y, кото-
рые оно соединяет, и записывается: u
i
=(x, y) или u
i
=(y, x).
→
U
– подмножество ориентированных линий, для которых
существенен порядок соединения вершин. Подмножество
→
U
называется подмножеством дуг. Причем каждая дуга u
i
∈
→
U
определяется упорядоченной парой (кортежем длины два) вер-
шин x
k
, y
l
, которые u
i
соединяет, и записывается: u
i
=(x
k
,y
l
).
Заметим, что u
i
=(x
k
,y
l
) и u
j
=(u
l
,x
k
) – это различные дуги в
графе G;
o
U
– подмножество линий, каждая из которых выходит и
входит в одну и ту же соответствующую этой линии вершину.
Называется
o
U
подмножеством петель.
Каждая петля u
i
принадлежит множеству
o
U
и может опре-
деляться упорядоченной парой, например вида u
i
=(x
k
,x
k
).
Граф состоит из вершин, которые на плоскости изобража-
ются нумерованными кружками или точками, и рёбер, изобра-
жаемых линиями (со стрелками или без стрелок), которые со-
единяют некоторые из этих вершин. Однонаправленное соеди-
нение ребром двух вершин называется дугой. Двунаправленные
или ненаправленные рёбра называются звеньями. Рёбра, соеди-
няющие вершину саму с собой, называются петлями.
Рёбра, подходящие к вершине х, называются инцидент-
ными данной вершине. Соответственно говорят, что вершина х
инцидентна рёбрам, подходящим к ней.
Количество рёбер, инцидентных вершине х, называется
степенью вершины s(x).
Вершина х называется изолированной, если её степень
s(x) равна нулю.
Граф является конечным, если он имеет конечное число
вершин и рёбер.
Бесконечные графы обладают следующими характеристи-
ками:
28
1.
Вершинами графа служат натуральные числа, причём
вершины p и q соединены звеном в том и только том случае,
если оба числа p и q простые и | p–q |
≤ 2. Множество вершин
этого графа счётно, а является ли множество рёбер счётным или
только конечным – неизвестно до сих пор (проблема близнецов
в теории чисел).
2.
Вершинами являются числа 1,2,...,n, а каждое действи-
тельное число x, удовлетворяющее условию i < x < i+1, служит
дугой из вершины i в вершину i+1. Граф содержит конечное
множество вершин и континуум рёбер (дуг).
3.
Вершинами служат все действительные числа, и при
фиксифованном
δ > 0 вершины x и y соединены ребром (звеном
или петлёй) тогда и только тогда, когда | x–y | <
δ. Каждому зна-
чению
δ отвечает свой граф, у которого множества вершин и
рёбер оба континуальны.
1.2
Классы
графов
Класс орграфов (ориентированных графов). Это граф
G=(X,U), у которого U =
∅.
Класс неорграфов (неориентированных графов). Это граф
G=(X,U), у которого
→
U
=
∅.
Класс смешанных графов. Это граф G=(X,U), у которого
U
⊂ U,
→
U
⊂ U и U ∪
→
U
⊆ U.
Класс мультиграфов. Мультиграф – это граф G=(X,U), у ко-
торого имеются параллельные (кратные) рёбра, т.е.
∃ x,y∈Χ⏐x u
k
y , x u
m
y,…, x u
p
y, u
k ,
u
m,…,
u
p
∈ U.
Для некоторых классов графов естественно определяется
понятие полного графа, как такого, который содержит все рёбра,
возможные при принадлежности графа данному классу и при
неизменном множестве вершин. Например, в случае p-графа
полнота означает, что при каждой вершине имеется ровно р
петель, а каждая пара различных вершин связана ровно р рёбра-
ми (среди них могут быть как звенья, так и дуги).
29
Граф общего вида, в котором две различные вершины все-
гда смежны, называется плотным.
Особо важную роль играют так называемые обыкновенные
графы. Граф этого класса характеризуется следующими че-
тырьмя свойствами:
1) он конечен;
2) он является неориентированным, т.е. не содержит дуг;
3) он не содержит петель;
4) он не содержит «параллельных» («кратных») рёбер; ина-
че говоря, никакие две его вершины не могут соединяться более
чем одним ребром (звеном).
Определение:
Обыкновенный граф – это неориентированный униграф без
петель. Униграф – это граф, в котором смежные вершины связа-
ны только одним неориентированным ребром.
Дополнительный граф. Дополнительным графом для обык-
новенного графа
)
,
(
U
X
L
=
называется обыкновенный граф
)
,
(
*
*
U
X
L
=
с тем же множеством вершин X и с множеством
U
y
x
X
y
x
y
x
U
\
}
&
,
/
~
{
*
≠
∈
=
рёбер. Иначе говоря, это такой
граф, в котором две различные вершины смежны тогда и только
тогда, когда они не смежны в исходном графе L.
Рассмотрим ещё одно важное в теории графов понятие–
скелет графа.
Скелет графа общего вида. В случае, когда при исследова-
нии графа L=(X.U;P) общего вида требуется не полная инфор-
мация о нём, а лишь знание того, какие пары его различных
вершин смежны и какие нет, прибегают к носителю такой ин-
формации – скелету графа L, который обозначим как
)
,
(
U
X
L
=
. Граф L относится к классу обыкновенных графов с
множеством вершин тем же, что и в графе L, и новым множест-
вом рёбер U , определённым следующим образом:
1)
если в графе L есть петли, то они удаляются;
2)
если в графе L есть дуги, то производится дезориентация
дуг;
30
3)
если в графе L есть кратные рёбра, то они заменяются
одним эквивалентным ребром-звеном;
4)
оставшиеся рёбра образуют множество рёбер U .
Таким образом, множество рёбер U состоит из рёбер, по-
лученных из множества U после выполнения описанных выше
процедур 1, 2, 3.
1.3
Способы
задания
графов
1.3.1 Геометрический
Основой геометрического способа задания графа является
рисунок, дающий визуальное изображение графа. Изображение
графа в виде рисунка наглядно раскрывает содержательный
смысл представляемого объекта. В этом способе вершины графа
изображаются точками (кружками), а рёбра – линиями (со
стрелками или без стрелок), концы которых подходят к верши-
нам графа.
1.3.2 Описание графа через предикат (инцидентор) P
Говорят, что задан граф G=(X,U,P), если дано множество
вершин Х, множество ребер U и трёхместный предикат (инци-
дентор) P, определяющий, какую пару вершин x
i
, x
j
, принадле-
жащих множеству вершин Х, соединяет ребро u
k
=(x
i
,x
j
). Инци-
дентор P удовлетворяет двум условиям:
А. Инцидентор P определён на всех таких упорядоченных
тройках элементов x, u, y, для которых x, y
∈ X и u ∈ U.
Б.
∀ u ∃ x, y {P(x, u, y) & ∀ x′, y′[P(x′, u, y′) ⇒ (x = x′ & y =
y
′) ∨ (x = y′ & y = x′)]}.
1.3.3 Матричный
1.3.3.1 Большинство задач автоматизации конструирования
схем удобно решать при использовании матричного способа
представления графов. Квадратная таблица R=//r
i,j
//
n*n
называет-