Материал: 5540

– множеством рёбер, каждое из которых представлено парой своих концевых вершин: Е1 = {(v1, v4), (v4, v3), (v3, v5), (v5, v2)}.

Порядок указания вершин при описании ребра здесь безразличен, так как все рёбра в графе G неориентированные.

В общем виде задать граф – значит описать множества его вершин и рёбер, а также отношение инцидентности. Для описания вершин и рёбер достаточно их занумеровать. Пусть v1, v2, ..., vj, ...,vn – вершины графа G; e1, e2, ..., ei, ...,em – рёбра. Отношение инцидентности задаётся:

– матрицей инцидентности ||εij|| размера m n: по вертикали и горизонтали указываются вершины и рёбра соответственно, а на пересечении i-й вершины и j-го ребра:

в случае неориентированного графа проставляется 1, если они инцидентны, и 0 – в противном случае, т.е.

(следует отметить, что в каждой строке матрицы количество единиц равно двум, а в каждом столбце равно степени вершины ρ1(vi ));

в случае орграфа: – 1, если вершина является началом ребра, 1 – если вершина является концом ребра, и 0 – если вершина является для ребра и началом, и концом (т.е. ребро – петля), проставляется любое

(в каждой строке сумма “+1” и “– 1” равна нулю, т. к. “+1” представляет вершину – исток, а “– 1” вершину – сток, а в каждом столбце матрицы инцидентности количество “+1” равно локальной степени ρ1(vi), а количество “– 1” равно локальной степени ρ2(vi)).

101

– списком рёбер графа, представленным двумя столбцами: в левом перечисляются все рёбра е i Е, а в правом – инцидентные ему вершины vi, vj; для н-графа порядок вершин в строке произволен, для орграфа первым стоит номер начала ребра:

– матрицей смежности ||δkl|| – квадратичной матрицей размера n n: по вертикали и горизонтали перечисляются все вершины vj V, а на пересечении k-й и l-й вершин в случае н-графа проставляется число, равное числу рёбер, соединяющих эти вершины; для орграфа δkl равно числу рёбер с началом в k-й вершине и концом в l-й.

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

Пример 5.2. Задать матрицами инцидентности и смежности графы G1 и G2 (см. рисунок 5.2).

Решение:

– матрицы инцидентности (таблицы 5.1, 5.2):

102

Задача 5.1. Граф задан списком рёбер:

103

2)определите степени вершин графа;

3)нарисуйте матрицу инцидентности графа;

2)нарисуйте матрицу смежности графа.

5.2 Операции над частями графа. Графы и бинарные отношения

Граф Н называется частью графа G, Н G, если множества его вершин V(H) и рёбер Е(Н) содержатся в множестве вершин V(G) и рёбер Е(G) соответственно, т.е. V(H) V(G) и Е(Н) Е(G).

Если V(H) = V(G), часть Н графа G называется суграфом.

Суграф Н является покрывающим для н-графа G, если любая вершина графа G инцидентна хотя бы одному ребру из Н.

Подграфом G(V′) графа G(V) с множеством вершин V′ V называется часть, которой принадлежат все рёбра обоими концами из V′.

Над частями графа G могут производиться следующие операции:

– дополнение Н к части Н – определяется множеством всех рёбер

общих вершин V(Н1) V(Н2) = Ø, а значит, и общих рёбер Е(Н1) Е(Н2) = Ø.

Части Н1 и Н2 не пересекаются по рёбрам, если Е(Н1) Е(Н2) = Ø. Если

V(Н1) V(Н2) = Ø, то сумма Н1 Н2 называется прямой.

Графы и бинарные отношения: отношению R, заданному на множестве V, взаимно однозначно соответствует ориентированный граф

G(R) без кратных рёбер с множеством вершин V, в котором ребро (vi, vj) существует, только если выполнено viRvj.

Пример 5.3. Какими особенностями отличается граф G, взаимнооднозначно соответствующий бинарному отношению R, если R:

а) симметрично;

104

б) антисимметрично; в) рефлексивно; г) антирефлексивно; д) транзитивно?

Решение. Пусть бинарное отношение R определено на множестве V

={v1, ..., vn}.

1.Симметричному отношению R взаимно однозначно соответствует

неориентированный граф без кратных рёбер G(R), в котором ребро (vi, vj) существует, если и только если выполнено viRvj (а значит, и vjRvi в силу симметричности R).

2.Антисимметричному отношению R взаимно однозначно соответствует ориентированный граф без кратных рёбер, не содержащий пар вершин с рёбрами, противоположно направленными к разным вершинам.

3.Если R рефлексивно, то граф G(R) без кратных рёбер имеет петли во всех вершинах.

4.Если R антирефлексивно, то граф G(R) без кратных рёбер не имеет

петель.

5.Если R транзитивно, то в графе G(R) без кратных рёбер для каждой пары рёбер (vi, vj) и (vj, vk) имеется замыкающее ребро (vi, vk).

Задача 5.2. Пусть ориентированный граф G на рисунке 5.4 задаёт отношение R : G(R). Каковы свойства отношения?

Рисунок 5.4 – Ориентированный граф G

105