Группы и их графы

Легко подсчитать число графов с фиксированным множеством вершин V. Эти графы различаются своими ребрами, и поэтому их число равно количеству подмножеств множества V×V, т.е., где п=|V|. Однако эти графы на всегда следует различать. Как в применении теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребра графа). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Такие графы называются изоморфными.

Пусть G и Н - графы, а φ: V G V H - биекция. Если для любых вершин и и v графа G их образы φ(u) и φ(v) смежны в Н тогда и только тогда, когда и и v смежны в G, то эта биекция называется изоморфизмом графа G на граф Н. Если такой изоморфизм существует, то мы пишем G@H и говорим, что графы G и Н изоморфны.

Очевидно, что отношение  изоморфизма графов является эквивалентностью, т.е. оно симметрично, рефлексивно и транзитивно. Следовательно, все графы разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т.е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игнорируется при введении понятия графа. Класс изоморфных графов принято называть абстрактным графом.

В некоторых случаях приходится различать изоморфные графы. Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, …, п. Отождествив каждую из вершин графа с ее номером (а, следовательно, множество вершин - с множеством чисел {1, 2, …, п}), определим равенство графов G и Н одного и того же порядка: G = Н тогда, когда ЕG = ЕН.

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

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

1. Явное задание графа как алгебраической системы.
2. Геометрический.
3. Матрица смежности.
4. Матрица инцидентности.

Рассмотрим  различные способы задания для  одного и того же графа.

1. Явное задание графа как алгебраической системы <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d}; { (a,b), (b,a), (b,c), (c,b), (a,c), (c,a), (c,d), (d,c) }>. В таком представлении ребру соответствуют две пары вершин (v₁,v₂) и (v₂,v₁), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы будем записывать как пару G(V,E), где V – множество вершин, а E – множество рёбер.

В дальнейшем будем опираться именно на второе определение графа.

2. Геометрический.

3. Матрица смежности.

Пусть G – помеченный граф порядка n, V={1, 2, 3, …, n}. Определим n×m–матрицу A=A(G), положив:

А_ij =

A(G) называется матрицей смежности графа G.  A=

4. Матрица инцидентности.

Пусть G(n,m)- граф, V={1, 2, 3, …,n}, E={l₁, l₂, l₃, …, l_n}. Опредилим  m×n – матрицу I=I(G) условиями

 I_kl =

I =

2. Маршруты, цепи и циклы

Маршрутом в графе G = <V,E; I> называется последовательность вершин и рёбер вида v₀,e₁,v₁,e₂, ..., v_n-1,e_n,v_n, где v_i V, i ∊ [0,n], e_i ∊ E, (v_i-1,e_i), (v_i,e_i) ∊ I, i ∊ [1, n]. Вершины v₀, v_n называются связанными данным маршрутом (или просто связанными). Вершину v₀ называют началом, а v_n – концом маршрута. Если v₀ = v_n, то маршрут называют замкнутым. Число n называется длиной маршрута.

Маршрут, в котором все  рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Маршрут, в котором все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

Минимальная из длин циклов графа называется его обхватом.

Для ориентированного графа  рассматривается понятие ориентированного маршрута – это последовательность v₀,e₁,v₁,e₂, ..., v_n-1,e_n,v_n, где v_i ∊ V, i ∊ [0,n], e_i ∊ E, (v_i-1,e_i), (v_i,e_i) ∊ I, i ∊ [1, n], в которой e_i=(v_i,v_i+1).Аналог цепи в этой ситуации – путь (ориентированная цепь), аналог цикла – контур (ориентированный цикл).

Пример 1.

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

Решение:

(1, 2) и (1, 2, 4, 7)- простые  циклы;

(1, 2, 4, 7, 8, 4)- цепь, не являющееся  простой;

(1, 2, 4, 7, 8, 4, 2)- маршрут, не  являющийся цепью;

(1, 2, 4, 1)- простой цикл;

Обхват графа равен 3.

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

Пример 2. (граф отношения делимости).

Построим граф, изображающее отношение делимости  на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип  такой: если от одного числа до другого  есть цепь, ведущая вверх, тогда второе число делится на первое. (рис. 8)

Граф называется связным, если любая пара его вершин связана.

Связными компонентами графа называются подграфы данного графа, вершины которых являются классами эквивалентности отношения свзанности в данном графе.

Цикломатическим числом графа называется число связных компонент графа плюс число рёбер минус число вершин.[3]

3. Деревья

Граф G = (V,E) называется деревом, если он связный и не содержит циклов. Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. Вершины степени 1 в дереве называют его листьями. Другие вершины называются внутренними вершинами.

Подграф G₁ = (V₁,E₁) графа G = (V,E) называется остовным деревом, если G₁ - дерево и V₁ = V.

Для (p, q)- графа G следующие утверждения эквивалентны:

1) G - дерево;

2) G - ациклическим и q = p-1;

3) G - связный и  q = p-1;

4) любые две  несовпадающие вершины графа  G соединяет единственная простая цепь;

5) G - без циклов, но при добавлении любого нового  ребра на тех же вершинах  появляется цикл.

Ориентированное дерево Т представляет собой свободный от петель ориентированный граф, соответствующий неориентированный граф которого является деревом, так что, если существует путь от вершины а к вершине b, то он единственный.

Предположим, что дерево представляет собой объект, подвижный  в вершинах, и подвесим дерево за одну из его вершин так, что остальная  его часть повиснет ниже этой вершины. Например, пусть задано дерево:

Если подвесить его  за вершину v₃, получится дерево, представленное на рис. 10, а). Если подвесить дерево за вершину v₄, оно будет выглядеть так, как показано на рис. 10, б).

Вершина в самой верхней  части каждого из изображений  называется корнем дерева. Если корень дерева определен, дерево называется корневым деревом. При необходимости можно заменить корневое дерево Т на ориентированное Т, при этом дерево на рис.11, в) будет заменено деревом на рис.11,г).

Такое дерево называется корневым ориентированным дерево Т, порожденным корневым деревом Т. При этом следует помнить, что это дерево отличается от неориентированного дерева и что вид ориентированного дерева зависит от выбора корня.

Если корень выбран, уровень вершины v определяется длинной единственного пути из корня в эту вершину. Высотой дерева называется длинна самого длинного маршрута от корня дерева до листа.

Если рассматривать корневое ориентированное дерево Т, порожденное данным корневым деревом Т, тогда вершина u называется родителем вершины v, а v называется сыном вершины u, если существует ориентированное ребро из u в v.

Если u – родитель v и v’, тогда v и v’ называются братьями. Если существует ориентированный маршрут из вершины u в вершину v, тогда u называется предком вершины v, а v называется потомком вершины u.

Если наибольшая из степеней выхода для вершин дерева равна m, тогда дерево называется m-арным деревом. В частном случае, когда m=2, дерево называется бинарным деревом.

Взвешенный граф – это граф, каждому ребру которого приписано действительное число, называемое весом ребра.[1]

4. Эйлеровы и гамильтоновы циклы

 Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем называть эйлеровым. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.

Например, граф, изображенный на рис. 12, является эйлеровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 1). В этом графе есть и другие эйлеровые циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода ребер.

Теорема 8 (Критерий эйлеровости графа). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин – чётные числа.

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

Кроме понятия эйлерова цикла  в задачах часто возникает  необходимость нахождения цепи, проходящей по каждому ребру ровно один раз (снимается требование замкнутости. Такие цепи будем называть эйлеровыми цепями.

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

Пример гамильтонова пути в графе и графа, в котором  такого пути не существует, показан  на рис. 13 (а), (б) соответственно.

5. Планарность.Двойственные графы

1. Планарные графы

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

Любой граф, изоморфный плоскому графу, называется планарным.

Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.

Границей грани будем считать множество вершин и ребер, принадлежащих этой грани. Например, граф, изображенный на рис. 14, имеет 4 грани:

Отметим, что всякий граф имеет одну и притом единственную неограниченную грань (на рисунке это грань 4). Такая грань называется внешней, а остальные грани - внутренними.

Данное понятие грани, по-существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник ``расплющиваем'' так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали ``исчезнет'', но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.

Таким образом, можно говорить о вершинах, рёбрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.

Когда мы говорим ``плоский  граф'', мы имеем в виду геометрический объект. Однако, конечно же не все  его геометрические свойства нам  важны (например, неважен абсолютный размер). Поэтому точнее считать, что  плоский граф – это трёхосновная модель <V,E,S; I, B>, где V – множество вершин, E – множество рёбер, S – множество граней, I – отношение инцидентности, а B – отношение ограниченности, связывающее рёбра с ограничиваемыми ими гранями.

2. Двойственные графы

Пусть G - планарный граф. Построим граф G* следующим образом. Число вершин графа G* равно числу граней G. Каждой грани G поставим в соответствие вершину G*. Вершины в G* смежны тогда и только тогда, когда соответствующие им грани в G граничат по ребру, причем две вершины G* соединяет столько ребер, сколько общих граничных ребер у соответствующих им граней. Граф G* называется двойственным (сопряженным) графу G.