Элементы графа, способы задания графа, подграфы

1. 3. Элементы графа, способы задания графа, подграфы

2. 3.1. Элементы графа

3.

Граф G – это совокупность двух множеств: не пустого множества
вершин V = {v1, v2,..., vn} и множества ребер (дуг) Е = {е1, е2,..., еm}.
Таким образом, G = (V, Е), V , Е VxV.
Если (v1, v2) – упорядоченная пара (т.е. дуга), то v1 называется началом,
a v2 – концом дуги е.
Если (v1, v2) – неупорядоченная пара, то ребро е называется
неориентированным.
Всякому графу G можно поставить в соответствие соотнесенный
неориентированный граф G` с теми же множествами V и Е и
инцидентностями, но все пары неупорядоченные.
Такой граф называется ассоциированным.

4.

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

5.

Примеры:
e6
v2
e1
v2
v6
v1
e2
e2
e3
e5
e4
v4
e4
e3
v5
v1
e1
e5
v3
v4
v3
v7
а) Ориентированный граф
б) Неориентированный граф

6.

На рисунке изображены: ориентированный псевдограф, имеющий 7
вершин и 6 дуг, и неориентированный мультиграф, имеющий 4 вершины и 5
ребер. Проиллюстрированы некоторые введенные понятия:
Для орграфа (рис. а): v1, v2, v3, v4, v5, v6 , v7 – вершины (узлы);
v5 – изолированная вершина; v1, v4 – концевые (висячие) вершины; v2 и v3, v2
и v1 – пары соседних вершин; е1, е2, е3, е4, е5, е6 – ориентированные ребра
(дуги); е2 и е3 – параллельные (кратные) дуги; е2 и е1 – смежные дуги;
е6 – петля.
Для графа (рис. б): v1, v2, v3, v4 – вершины; v4 – концевая (висячая)
вершина; v2 и v3, v2 и v1 – пары смежных вершин; е1, е2, е3, е4, е5 – ребра
(дуги); е4 и е5 – параллельные (кратные) ребра; е2 и е3 – смежные ребра;
петель нет.

7. 3.2. Способы задания графов

8.

1) Для наглядности граф представляют в виде геометрического объекта:
вершинам соответствуют различные выделенные точки в пространстве (на
плоскости), ребрам – отрезки кривых, связывающие соответствующие
вершины.
2) Перечисление (список) ребер графа с указанием их концов и
добавлением списка изолированных вершин.
3) Матрица смежности A = (аij) квадратная матрица размера nxn (где n –
число вершин).
Для ориентированного графа:
1, если из вершины i в вершину j заходит дуга ,
0, если условие нев ыполнено.
aij =
Для неориентированного графа:
1, если вершины i и j соединены ребром,
aij = 0, если условие невыполнено.

9.

4) Матрица инцидентности B = (bij) называется прямоугольная матрица
(n m), где n – число вершин, m – число ребер.
Для ориентированного графа:
1, если вершина vi является началом дуги e j ;
bi,j = 1, если вершина vi является концом дуги e j ;
0, если вершина vi не инцидентна дуге e j ;
Для неориентированного графа:
1, если вершина vi инцидентна ребру e j ;
bi,j =
0, если вершина vi не инцидентна ребру e j .
Петле соответствует элемент, равный 2.

10.

Пример. Матрицы смежности и инцидентности графа, изображенного
на рис. а, имеют вид:
0 0 0 0 0 0 0
1
0
1
0
0
0
0
0 0 0 0 0 0 0
A 0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
1 0 0 0 0 0
1
1
1
0
0
0
0 1 1 0 0 0
B 0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 1 2
0 0 0 1 1 0