Глава 6

Определения и примеры

6.1 Определения графа

Пусть даны два множества X; Y , и на них зада-

но отношение R µ X £ Y . Граф G обозначается как тройка G = hX; Y; Ri, или G = (X; Y; R). Чаще, однако, полагают X = Y и R µ X £ X; тогда G = (X; R).

Определение. Граф G = (X; R) задан, если заданы множество X и бинарное отношение R на X.

Элементы множества X называются вершинами. Элементы мно-

!

жества R – упорядоченные пары вершин hx; yi, или (x; y), или xy называются дугами. Пара (x; x) называется петлей.

Говорят, что дуга (x; y) исходит из вершины x и заходит в вершину y, или дуга соединяет вершины x и y.

Пример 6.1.

X = fa; b; c; d; eg; R = f(a; e); (a; d); (b; a); (b; c); (c; c),(d; a), (d; b); (d; c)g J

Определение. Граф G = (X; ¡) задан, если заданы множество X и отображение ¡ : X 7!X.

Здесь X – множество вершин; множество пар (x; y), для которых x 2 X; y 2 ¡x – это множество дуг; пары

(x; x), x 2 ¡x – петли.

Пример 6.2.

X = fa; b; c; d; eg; ¡a = fc; dg, ¡b = fb; cg, ¡c = ?, ¡d = fag, ¡e = feg. Дуги: (a; c); (a; d); (b; c); (d; a); петли: (b; b); (e; e). J

Для иллюстрации вершины графа изображаются в виде точек

194 Глава 6. Определения и примеры

Здесь X – множество вершин, U – множество ребер, P (x; u; y)

– инцидентор графа G. Высказывание P (x; u; y) читается так: ребро u соединяет вершину x с вершиной y, или ребро u соединяет упорядоченную пару вершин hx; yi.

Условие 2 говорит о том, что каждое ребро графа соединяет какую-либо пару вершин (x; y), но кроме этой пары может (хотя и необязательно) соединять еще только обратную пару (y; x). Для любого ребра u 2 U истинно одно и только одно из трех следующих высказываний:

8u 2 U

9x; y 2 X[x 6= y ^ P (x; u; y) ^ :P (y; u; x)]

9xP (x; u; x)

9x; y[x =6 y ^ P (x; u; y) ^ P (y; u; x)]:

В соответствии с этим множество ребер U разбивается на три

¡! ± »

попарно непересекающихся подмножества U , U, U, которые на-

зываются, соответственно, множествами дуг, петель´ и звеньев. Если для некоторой тройки элементов x; u; y истинно высказывание P (x; u; y), т.е. ребро u соединяет вершину x с вершиной y, то

¡!

² если u 2 U S, то говорят: дуга u исходит из вершины x и заходит в вершину y, или дуга u идет из вершины x в вершину y ;

±

² если u 2 U, т.е. x = y, то говорят: u есть петля при вершине x;

»

² если u 2 U, то говорят: вершины x; y соединены звеном u.

Пример 6.3.

du11 mc

Рис. 6.3. Граф по Зыкову

X = fa; b; c; d; eg, Истинны следующие высказывания:

P (a; u1; a); P (a; u2; a); P (a; u3; c); P (b; u4; c), P (c; u4; b), P (c; u5; b), P (c; u11; c); P (a; u7; d); P (d; u7; a), P (a; u8; d),

P (d; u6; a), P (e; u9; e); P (e; u10; e). J

Две вершины x; y называются смежными, если существует по крайней мере одно соединяющее их ребро, т.е. если истинно высказывание

J(x; y) , 9u[P (x; u; y) _ P (y; u; x)];

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

С помощью инцидентора P определяются еще три двуместных предиката:

I+(x; u) , 9zP (x; u; z), I¡(x; u) , 9zP (z; u; x), I±(x; u) , P (x; u; x),

а также двуместный предикат

I(x; u) , I+(x; u) _ I¡(x; u)

Если истинно указанное высказывание, то говорят

I+(x; u) – дуга u исходит из вершины x;

I¡(x; u) – дуга u заходит в вершину x;

I±(x; u) – u есть петля при вершине x.

При произвольном u 2 U говорят, что ребро u и вершина x инцидентны, если I(x; u) истинно, т.е. ребро соединяет вершину x хотя бы с одной вершиной y (может быть x = y).

Два ребра u; v называются смежными , если существует хотя бы одна инцидентная им обоим вершина, т.е. если истинно высказывание

9x[I(x; u) ^ I(x; v)].

З а м е ч а н и е. Определение 2 (стр. 193)

6.1.4 Части графа

Пусть X0 µ X и U0 µ U – подмножества вершин и ребер графа

G = (X; U; P ) , а P 0 – предикат, индуцированный инцидентором P

на этих подмножествах. Если X0 и U0 выбраны так, что они вместе с P 0 удовлетворяют всем условиям определения графа, то граф G0 = (X0; U0; P 0) называется частью графа G, порожденной подмножествами X0 и U0. Очевидно, что включив в U0 некоторое ребро

графа, необходимо также включить в X0 те вершины, которые соединяются этим ребром. К числу частей графа G относится и сам G. Остальные части – собственные или правильные. Предикат P 0, индуцированный предикатом P , будем далее обозначать P .

Наиболее часто рассматриваемые части имеют собственные названия.

Определение. Часть G0 = (X0; U0; P ) называется подграфом графа G, порожденным подмножеством вершин X0 µ X, если при образовании части G0 сохранены все те ребра, которые соединяют между собой сохраненные вершины.

Определение. Часть G0 = (X0; U0; P ) называется суграфом, порожденным подмножеством ребер U0 µ U, если X0 = X.

Части графа можно определить и так: введем следующие операции над элементами графа.

1. Удаление вершины с инцидентными ей ребрами:

X0 = X n fxg; U0 = U n fujI(x; u)g.

2. Удаление ребра: U0 = U n fug; X0 = X.

Тогда подграф G0 = (X0; U0; P ) образуется из G удалением некоторых вершин;

суграф G0 = (X; U0; P ) образуется из G удалением некоторых ребер;

часть G0 = (X0; U0; P ) образуется из G удалением некоторых вершин и/или ребер (подграф, суграф, подграф суграфа, суграф подграфа).

Сам граф по отношению к подграфу называется надграфом, по отношению к суграфу – сверхграфом, по отношению к части –

объемлющим графом .

Пример 6.4.

Граф G = (X; U; P ); X = fa; b; c; d; eg; U = f1; 2; : : : ; 7g;

P= fP (a; 1; b), P (a; 6; d), P (d; 6; a), P (b; 3; c), P (c; 2; b), P (b; 4; d), P (d; 4; b),

P(d; 5; a), P (e; 7; e)g.