учебное пособие - теория графов

Пример 5.8.

граф G1 получен из графа G с помощью операции удаления вершины a, если G1 (V \{a}, R \{(b,c) | b a или c a}) , и обозначается:

G1 G a .

31

Пример 5.9.

Определение 5.10. Пусть G (V , R) – граф. Говорят, что граф G1 получен из графа G добавлением вершины a, если G1 (V {a}, R) , и обозначается: G1 G a .

Пример 5.10.

Замечание 5.2. Для операций 3) и 4) справедливы свойства аналогичные леммам 5.1 и 5.2.

Определение 5.11.

1.Пусть G (V , R) – граф и u (a,b) R , c V . Говорят, что граф G1 получен из графа G с помощью операции введения вершины c в ребро

u (a,b) (или с помощью операции подразделения ребра u), если

G1 (V {c},(R \{u}) {(a,c),(c,b)}) .

2. Граф G1 называется подразделением графа G, если G1 может быть получен из G путем применения конечного числа операций подразделения ребер.

32

Пример 5.11.

Определение 5.12.

1.Пусть G (V , R) – граф, a, b V , a V , G1 (V1, R1 ) (G a) b . Говорят, что граф G2 получен из графа G с помощью отождествления

2.Если вершины a и b в графе G соединены ребром, то операция отождествления вершин a и b называется операцией стягивания ребра (a,b)

.

Пример 5.12.

y V } {( y, a ) | ( y, a) R и y V }. 33

Пример 5.13.

G (V , V 2 \ (R )) .

Пример 5.14.

Замечание 5.3. Граф G называют также дополнительным графом для графа G.

Определение n-мерного куба

Из полного графа K2 с помощью операции произведения графов получают важный класс графов, называемых n-мерными кубами. n- мерный куб определяется индуктивно следующим образом.

Определение 5.15.

1)Нульмерным кубом Q0 называется неорграф без петель, состоящий из одной вершины;

2)граф Q1=K2 называется 1-мерным кубом;

34

3)граф Q2= K2 Q1 называется 2-мерным кубом; и т.д.

4)граф Qn= K2 Qn 1 называется n-мерным кубом, n >1.

Пусть граф K2 имеет вершины 0 и 1. Тогда вершинами n-мерного куба являются всевозможные упорядоченные n-ки, состоящие из нулей и единиц, а ребра задаются по правилу: вершины смежны тогда и только тогда, когда соответствующие кортежи отличаются ровно одной координатой.

§6. Изоморфизм графов

Содержание параграфа

гомоморфизм, изоморфизм и гомеоморфизм графов;

простейшие свойства изоморфных графов;

изоморфизм мультиграфов;

установление изоморфизма графов с помощью матрицы смежности.

Определение 6.1. Пусть G=(V,R), G1=(V1,R1) – графы. Отображение

φ: V1 V2 называется гомоморфным отображением графа G в граф G1

или гомоморфизмом графа G в граф G1, если a, b V: (a, b) R ( (a) , (b) ) R1.

Пример 6.1. Пусть графы G=(V,R) и G1=(V1,R1) имеют вид:

35

Следовательно, φ – гомоморфизм G в G1.

Определение 6.2. Пусть G=(V,R), G1=(V1,R1) – графы. Биективное отображение φ: V1 V2 называется изоморфным отображением графа

Отображение : V V1 задано по правилу: (1) a , (2) c ,(3) b . Тогда

(1,2) R ( (1) , (2) ) =(b, a) R1, (3,1) R ( (3) , (1) ) = (c, a) R1.

Поскольку отображение инъективно и сюръективно, то – изоморфизм G на G1.

Определение 6.3. Графы G и G1 называются изоморфными и обозначаются G G1, если существует изоморфизм G на G1.

36

Лемма 6.1. Пусть G=(V,R), G1=(V1,R1) – графы, – изоморфизм G на G1. Тогда справедливы следующие утверждения:

1)|V1| = |V2|, |R1| = |R2|;

2)a V: deg a deg (а) , deg a deg (a) , т.е. deg a deg (a) .

Лемма 6.2. Отношение изоморфизма на множестве всех графов является отношением эквивалентности.

Замечание 6.1. Обычно на практике графы рассматриваются с точностью до изоморфизма.

Определение 6.4. Графы G и G1 называются гомеоморфными, если они обладают изоморфными подразделениями.

Определение 6.5. Пусть G=(V, U, f ), G1=(V1, U1, f1) – ориентированные мультиграфы. Мультиграфы G и G1 называются изоморфными, если существуют биекции : V V1 и ψ: U U1 такие, что a, b V,

u U: f (a,b)=u f1( (a), (b))= ψ(u).

Установление изоморфизма графов с помощью матрицы смежности

Напомним определение подстановки n-ой степени.

Определение 6.6. Пусть M 1, 2, ..., n . Подстановкой на множестве M или подстановкой n-й степени называется взаимно одно-

значное отображение множества M на M.

Пусть : M М – подстановка. Тогда k M: (k)=ik . Под-

Теорема 6.1. Пусть G=(V,R), G1=(V1,R1) – графы, V={ a1, a2 ,..., an },

G и G1 соответственно. Тогда G G1 в том и только том случае, когда

37

G1. Теорема доказана.

Следствие 6.1.1. Два графа являются изоморфными тогда и только тогда, когда их матрицы смежности можно получить одну из другой с помощью одновременной перестановки строк и столбцов.

§ 7. Маршруты графов

Содержание параграфа

определение маршрута графа;

маршруты орграфов (пути, контуры);

бесконтурный граф;

маршруты неорграфов (цепи, циклические маршруты, циклы);

ациклический граф;

обхват неорграфа;

понятие обхода графа;

нахождение в графах маршрутов с заданным количеством ребер;

матрица маршрутов длины k.

Определение 7.1.

1.Пусть G=(V,R) – граф, a1,a2,…,an+1 V, ui=(ai,ai+1) R, i 1, n . После-

довательность (a1,u1,a2,u2,…,an,un,an+1) (1) называется маршрутом графа G, соединяющим вершины a1 и an+1, или иначе (a1,an+1)-

маршрутом.

2.Число n ребер в маршруте (1) называется длиной маршрута (1).

Маршруты также можно обозначать следующим образом

(1): (a1,a2,…,an,an+1) или (1): (u1,u2,…,un).

39

Возможно, что n=0, т.е. маршрут (1) может иметь вид: (a1).

Маршруты ориентированных графов

Определение 7.2. Маршрут орграфа G называется путём, если все его рёбра попарно различны.

Определение 7.3. Путь орграфа G называется контуром, если первая вершина пути совпадает с последней.

Замечание 7.1. Полагают, что маршрут нулевой длины контуром не является.

Лемма 7.1. Если орграф не имеет контуров, то в нем имеется вершина, полустепень захода в которую равна 0.

Взаимосвязь между данными понятиями можно изобразить в виде схемы:

Схема 1.

Определение 7.4. Орграф, не содержащий контуров, называется

бесконтурным.

Пример 7.1.

(1, 3, 2, 1) – контур,

(1, 3, 4, 5) – путь, не являющийся контуром, (1, 3, 2, 1, 3) – маршрут, не являющийся путем.

40