Материал: Дискретная математика. учебное пособие. Собенина О.В

Пример. Для графов G₁ =({x₁, x₂, x₃}, {(x₁,x₂), (x₂,x₃)}) и G₂=({x₁,x₂,x₄}, {(x₁,x₂), (x₄,x₁)}) (рис. 4.17) найдем , , . По определению имеем

=({x₁,x₂,x₃,x₄},{(x₁,x₂), (x₂,x₃) ,(x₄,x₁)}),

=({x₁,x₂}, {(x₁,x₂)}),

=({x₁,x₂,x₃,x₄}, {(x₂,x₃), (x₄,x₁)}).

4. Соединением графов G₁+G₂ называется граф {(x_i, x_j) | x_iX₁, x_jX₂, x_i  x_j}).

Пример. Для графов G₁ и G₂, показанных на рис. 4.18а, соединением G₁+G₂ является граф, представленным на рис. 4.18б.

5. Произведением графов G₁ и G₂ называется граф , в котором ((x₁, y₁), (x₂, y₂))V тогда и только тогда, когда x₁=x₂ и (y₁, y₂)V₂, или y₁=y₂ и (x₁, x₂)V_1.

П ример. На рис. 4.19 изображено произведение графов G₁=({1, 2}, {(1, 1), (2, 1)}) и G₂ = ({a, b, c},{(a, b), (b, a), (b, c)}).

2. Унарные операции.

1. Удаление вершины. При удалении вершины из графа удаляются и все инцидентные ей ребра (дуги). Пусть – граф и . Удалить вершину x из графа G – это значит построить новый граф , в котором и получается из V удалением всех ребер, инцидентных вершине x. Пример удаления вершины x из графа:

До удаления вершины x После удаления вершины x

2 . Удаление ребра (дуги). Пусть – граф и . Удалить ребро (дугу) v – это значит построить новый граф , в котором и . Вот иллюстрация удаления ребра графа:

До удаления ребра v. После удаления ребра v

При удалении ребра (дуги) его концевые вершины не удаляются. Операцией, являющейся обратной к удалению ребра, является добавление ребра.

3. Слияние или отождествление вершин. Говорят, что вершины и в графе G отождествляются (сливаются), если они заменяются такой новой вершиной , что все ребра (дуги) графа, инцидентные и , становятся инцидентными новой вершине .

4. Стягивание ребра (дуги). Эта операция означает удаление ребра и отождествление его концевых вершин. Граф G₁ называется стягиваемым к графу G₂, если граф G₂ может быть получен из G₁ в результате некоторой последовательности стягиваний ребер.

П ример. Из графа G, показанного на рис. 4.20, добавлением вершины 5 образуется граф G₁, добавлением дуги (3,1) – граф G₂, удалением дуги (3,2) – граф G₃, удалением вершины 2 – граф G₄, отождествлением вершин 1 и 4 – граф G₅, стягиванием дуги (2,3) – граф G₆.

5. Подразбиение ребра. Пусть – граф и . Выполнить подразбиение ребра v – это значит построить новый граф , в котором (т.е. z – некая новая вершина) и . С графической точки зрения эта операция означает «внесение в ребро новой вершины». Вот графическая иллюстрация:

x x

z

y y

До внесения вершины z После внесения вершины z

Граф называется дополнением простого графа, если ребро (x_i, x_j) входит в в том и только в том случае, если оно не входит в V. Другими словами, две вершины смежны в тогда и только тогда, когда они не смежны в G.

Пусть G’=(X’,V’) является подграфом графа G=(X,V). Подграф G’’=(X,V \V’) графа G называется дополнением графа G’ в графе G.

4.6. Метрические характеристики графа. Расстояние в графах

Пусть G=(X,V) – связный неорграф, x_i, x_j – две его несовпадающие вершины. Длина кратчайшего (x_i, x_j) –маршрута называется расстоянием между вершинами x_i, и x_j и обозначается через р(x_i, x_j). Положим р(x_i, x_i)=0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

p(x_i, x_j)0;

р(x_i, x_i ) = 0 тогда и только тогда, когда x_i,=x_j;

p(x_j,x_i,) = p(x_i, x_j) (симметричность):

p(x_i, x_j)p(x_i, x_k)+p(x_k, x_j) (неравенство треугольника).

Если X={x₁,x₂, …, x_n}, то матрица Р=(p_ij), в которой p_ij=p(x_i,x_j), называется матрицей расстояний. Заметим, что Р^T=Р, т. е. матрица Р симметрична.

Для фиксированной вершины x_i, величина е(x_i)= =max{p(x_i, x_j) | x_j X} называется эксцентриситетом вершины x_i. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее. Если Р – матрица расстояний, то эксцентриситет е(x_i) равен наибольшему из чисел, стоящих в i-й строке.

Максимальный среди всех эксцентриситетов вершин назы­вается диаметром графа G и обозначается через d(G): d(G)=max{e(x_i) | x_i  X}. Вершина x_i называется периферийной, если e(x_i)=d(G).

Пример. Найдем диаметр графа G, изображенного на рис. 4.21. Матрица расстояний Р имеет вид

отсюда е(1)=3, е(2)=2, е(3)=3, е(4)=2, е(5)=2 и, следовательно, d(G)=3. Вершины 1 и 3 являются периферийными.

Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r(G): r(G) = min{e(x_i) | x_iМ}. Вершина x_i называется центральной, если е(x_i)=r(G). Множество всех центральных вершин графа называется его центром.

Примеры.

1. Радиус графа, показанного на рис. 4.21, равен 2, а его центром является множество {2,4,5}.

2. В полном графе К_п все различные вершины смежны, и поэтому d(K_n) = r(К_n) = 1.

Задача нахождения центральных вершин возникает в практической деятельности людей. Пусть, например, граф представляет собой сеть дорог, т. е. вершины соответствуют населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т. п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной тем, что приходится учитывать и другие обстоятельства – расстояния между населенными пунктами, стоимость, время проезда и т. д. Для учета этих параметров используются взвешенные графы [4].

Пусть G = (X,V) – взвешенный граф, в котором вес каждой дуги (x_i,x_j) есть некоторое вещественное число (x_i,x_j). Весом маршрута x₁, x₂, ... , x_n, x_n+1, называется число . Взвешенным расстоянием ( - расстаянием) p_(x_i,x_j) между вершинами x_i и x_j называется минимальный из весов (x_i,x_j)-маршрутов. (x_i,x_j)-маршрут, вес которого равен расстоянию p_(x_i,x_j), называется кратчайшим (x_i,x_j)-маршрутом в взвешенном графе G. Взвешенным эксцентриситетом e_ (x_i) вершины x_i называется число mах{p_(x_i,x_j) | x_jМ}. Взвешенной центральной вершиной графа G называется вершина x_i, для которой е_(x_i)=min{е_(x_j) | x_j М}. Взвешенный эксцентриситет центральной вершины называется взвешенным радиусом графа G и обозначается через r_(G).

4.7. Графы с заданной последовательностью степеней

Степенной последовательностью графа называется список степеней его вершин. Часто по степеням вершин графа можно судить о его строении. Естественно возникают следующие вопросы. Как связать между собой степени вершин графа? Как по списку степеней графа судить о его строении? Какова связь между графами с совпадающими списками степеней вершин? Можно ли построить граф с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами и как это сделать?

Последовательность неотрицательных целых чисел называется графической, если существует граф с такими вершинами , что вершина имеет степень . Этот граф называется реализацией последовательности .