Множества. Комбинаторика. Отношения (стр. 21 )

3)  Можно ли 7 человек соединить телефонной связью таким образом, что каждый из них связан ровно с тремя другими. (Указание: задача равносильна построению графа с 7 вершинами, степени которых равны трем. См. упражнение 2).

Если deg=0, то – изолированная вершина. Если deg=1, то – концевая вершина. Если все вершины имеют одинаковую степень r, то граф называют регулярным (однородным) степени r. Пример графа степеней 1, 2, 3.

3.1.2 Способы задания графа

Задать граф – описать множества его вершин и рёбер, а также отношения инцидентности. Для описания конечных графов достаточно перенумеровать вершины и рёбра.

Способ 1. Пусть – вершины графа G, x1, … , xh – рёбра. Отношение инцидентности можно определить матрицей инцидентности , имеющей h строк и n столбцов. Если ребро x инцидентно вершине , то =1, в противном случае =0. В матрице инцидентности ориентированного графа G, если вершина – начало ребра xi , то =-1, а если конец ребра, то +1. Если xi – петля, а – инцидентная ей вершина, то , где – любое число, отличное от 1,0, -1. В остальных случаях =0.

Способ 2. Отношение инцидентности можно задать списком рёбер графа. Каждая строка этого списка соответствует ребру, а в ней записаны номера вершин, этому ребру инцидентных.

Способ 3. В матрице смежности графа столбцам и строкам соответствуют вершины графа. Элемент этой матрицы равен количеству рёбер, инцидентных i-й и j-й вершинам, если в графе допускаются кратные рёбра. Для ориентированного графа этот элемент равен количеству рёбер с началом в вершине i и концом в вершине j.

3.1.3 Изоморфизм графов

Пусть даны два графа . Графы G1 и G2 называются изоморфными, если существуют взаимнооднозначные соответствия между множествами вершин и множествами рёбер этих графов, при которых соответствующие рёбра соединяют соответствующие вершины, т. е. если , , то =().

Изоморфизм графов обозначаем G1 » G2. Множество всех графов разбивается на непересекающиеся классы изоморфности графов.

Пример. Все представители классов изоморфности орграфов с тремя вершинами и тремя рёбрами:

Изоморфизм графа называется автоморфизмом графа. Все автоморфизмы графа образуют группу относительно операции композиции отображений.

Упражнения

1)  Разработать порядок перебора и перечислить все попарно неизоморфные трёхвершинные, четырёхвершинные и пятивершинные графы (4; 11; 34).

2)  Перечислить все попарно неизоморфные двух-, трех-, четырехреберные графы без изолированных вершин.

3)  Изоморфны ли графы G1 и G2:

(1) G1 : 14 16 23 25 26 45; G2 : 16 15 26 24 35 34.

(2) G1 : 12 23 24 15 34 45; G2 : 12 23 51 25 41 34.

Дополнение графа G имеет в качестве множества вершин множество V, а две вершины в смежны Û, не смежны в G.

Пример.

Самодополнительный граф – это граф, который изоморфен своему дополнению. Наименьшие по числу рёбер нетривиальные самодополнительные графы.

Примеры самодополнительных четырехвершинных и пятивершинных графов:

Задача Рамсея. Доказать, что среди шести человек найдутся трое попарно знакомых или попарно незнакомых.

Решение. Шестивершинный граф, либо его дополнения содержат треугольник.

3.1.4 Подграф, маршрут, цепь, цикл

Граф называется подграфом графа , если , . Подграф, не совпадающий ни самим графом G и не являющийся пустым, называется собственным подграфом графа G. Подграф, содержащий все вершины графа, называется остовным. Маршрутом (путём) длины называется последовательность вершин и рёбер где ребро соединяет вершины и , ,, – начало пути, – конец. Если , то маршрут называется замкнутым. Если , то маршрут называется открытым. Открытый маршрут, в котором все вершины различны, называется цепью. Маршрут, в котором все рёбра различны, называется простым. Замкнутый (простой) маршрут называется циклом (простой цикл или элементарный). Если существует маршрут, соединяющий две вершины, то из рёбер этого маршрута можно построить цепь (для этого следует выбрать маршрут минимальной длины из рёбер данного). Длина кратчайшей цепи, соединяющей вершины a и b, называется расстоянием между этими вершинами . Если рёбра a и b не соединены цепью, то .

Свойства расстояния:

(1) ;

(2) ;

.

Пусть S – некоторое непустое множество вершин V графа , а – совокупность рёбер графа, обе вершины которых . Подграф графа G называется подграфом, порождённым S.

3.1.5 Связность

Граф называется связным, если между любыми двумя различными его вершинами существует цепь. На множестве вершин графа определим отношение , считая, что, если , если или если в графе существует цепь, соединяющая a и b. Отношение является отношением эквивалентности. Пусть – классы эквивалентности множества вершин графа , определяемые этим отношением. Подграфы ,…, графа G называются компонентами связности этого графа, а их число называется степенью связности графа. Если граф имеет несколько компонентов связности, то вершины можно перенумеровать так, что его матрица инцидентности клеточно диагональна.