Элементы теории графов

3.1 Определения графов

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

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

3.1.1 История теории графов

Теория графов возникла из решения различных прикладных задач. Первые задачи были связаны с решением математических развлекательных задач и головоломок. Рассмотрим эти задачи (пояснить подробнее)

1. Задача о Кенигсбергских мостах. Необходимо обойти все 4 части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Ее развитие привело к циклу задач об обходах графов (Леонард Эйлер, 1736 г.).

2. Задача о трех домах и трех колодцах. Есть три дома и три колодца. Жители домов поссорились. Требуется от каждого дома проложить тропинку к каждому колодцу так, чтобы эти тропинки не пересекались. (Куратовский, 1930)

3. Задача о четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одинаково. Эта задача была сформулирована в середине XIX века, и попытки ее решить привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение.

Многие результаты середины XIX века были получены при решении практических проблем. (Например, Кирхгоф: система уравнений токов и напряжений в электротехнической схеме представлялась графом и решалась с помощью методов теории графов; химия… Задача о перевозках, решение которой привело к созданию эффективных методов решения транспортных задач …). В XX веке задачи, связанные с графами, получили распространение не только в физике, электротехнике, химии, биологии, экономике, но и внутри различных разделов математики (алгебра, теория чисел, теория вероятностей и др.).

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

3.1.2 Основные понятия

Граф G определяется как упорядоченная пара áV, Eñ, где V – непустое множество вершин, отношение – множество ребер (набор неупорядоченных или упорядоченных пар вершин). Вершины и ребра графа называются его элементами.

Граф, содержащий конечное число элементов, называется конечным. Число вершин конечного графа называется его порядком и обозначается | V |, число ребер обозначается как |E |: G(V,E) = áV, Eñ, V ¹ Æ, E Ì V´V, E = E–1.

Граф порядка n, имеющий m ребер, называется (n,m)-графом.

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

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

Пусть v1 и v2 – вершины, e – соединяющее их ребро. Тогда ребро e и каждая из этих вершин называются инцидентными друг другу, вершины v1 и v2 называются смежными. Два ребра, имеющие одну общую вершину (инцидентные одной вершине), также называются смежными.

Пример 3.1 Вершины v1 и v2 являются смежными,
вершина v1 инцидентна ребрам e2= (v1,v2) и e1= (v1,v3). =
{e1, e2, e3, e4}. Ребра e1, e2, e3 являются попарно смежными, а ребра e2, e4 – несмежными, так же как и вершины v1, v4 и v2, v4.

Множество вершин, смежных с вершиной v, называется множеством смежности (окружением) вершины v и обозначается Г+(v) ={uÎV| (u,vE}, Г(v)=Г*(v) =Г+(v)È{v}. Очевидно, что: u Î Г(v) Û v Î Г(u). Если не оговорено противное, то подразумевается Г+ и обозначается просто Г.

Если А – множество вершин, то Г(А) – множество вершин, смежных с вершинами из А: Г(А) = {uÎV| $vÎA uÎГ(v)} = ÈГ(v) "vÎA.

лекция 9(7.04.05)

3.1.3 Другие определения графов и бинарные отношения

Часто рассматриваются следующие разновидности графов.

1. В некоторых задачах инцидентные ребру вершины рассматриваются в определенном порядке. Тогда элементами множества Е={(u,v)|u,vÎV} являются упорядоченные пары, т.е. ребру приписывается направление от одной вершины к другой, и ребра называются дугами (говорят, что дуга выходит из вершины u и заходит в вершину v). Вершины в таком графе называются узлами, а сам граф, все ребра которого являются дугами, называется ориентированным графом, или орграфом (см. рис. а)). Иногда рассматриваются и смешанные графы, имеющие как дуги, так и неориентированные ребра.

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

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

4. В отличие от мультиграфа и псевдографа, граф без петель и кратных ребер называется простым.

 
 

г)
в)
б)
а)
5. Если задана функция F : V ® M или F : Е ® M, то множество М называется множеством пометок, а сам граф называется размеченным (т.е. всем его вершинам или всем ребрам присвоены некоторые метки, в качестве которых обычно используются буквы или целые числа – г)).

Далее, говоря «граф G(V,E)», будем иметь в виду неориентированный непомеченный граф без петель и кратных ребер.

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

Любой граф с петлями, но без кратных ребер, задает бинарное отношение E на множестве V, и обратно. Пара элементов принадлежит отношению: (a,b)ÎEÌV´V Û в графе есть G ребро (a,b). Неориентированный граф соответствует симметричному отношению. Изменение направления всех дуг соответствует обратному отношению. Мультиграф, все вершины которого имеют петли, задает рефлексивное отношение.

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

При изображении графа точки, обозначающие его вершины, берутся совершенно произвольно, поэтому рисунки одного и того же графа могут быть совершенно непохожими. Как же понять, одинаковы ли графы, изображенные разными чертежами? Решение проблемы стандартное – если можно взаимно однозначно отобразить множество вершин одного графа на множество вершин другого так, чтобы сохранилось отношение смежности, то это две копии графа.

Говорят, что два графа G1(V1,E1) и G2(V2,E2) изоморфны: G1~ G2, если существует биекция (1-1 соответствие) h: V1®V2, сохраняющая отношение инцидентности (при которой смежные вершины (ребра) графа G1 переходят в смежные вершины (ребра) графа G2): e1 =(u,v)Î E1 Þ e2 =(h(u),h(v))Î E2; e2 =(u,v)Î E2 Þ e1 = (h–1(u),h–1(v))Î E1;

Графы, отличающиеся только нумерацией вершин, являются изоморфными.

Изоморфизм графов является отношением эквивалентности. Действительно, изоморфизм обладает всеми необходимыми свойствами: 1) рефлексивность – G~G, где требуемая биекция есть тождественная функция;
2) симметричность – если G1~ G2 с биекцией h, то G2 ~ G1 с биекцией h–1;
3) транзитивность – если G1~ G2 с биекцией h, а G2 ~ G3 с биекцией g; то G1~ G3 с биекцией g h.

Графы рассматриваются с точностью до изоморфизма, т.е. рассматриваются классы эквивалентности по отношению изоморфизма.

Пример 3.2 Три внешне различные диаграммы, приведенные на рисунке, являются диаграммами одного и того же графа.

Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. В частности, количество вершин и количество ребер – инварианты графа G.

Ñ Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.

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

3.2 Элементы графов

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

3.2.1 Валентность

Степенью (или валентностью) вершины v называется число инцидентных ей ребер. Степень вершины обозначается deg(v). Очевидно, что для любой вершины vÎ V справедливо: 0 £ deg(v) £ |V| –1; deg(v) = |Г(v)|.

Вершина графа, имеющая степень 0, называется изолированной, а вершина со степенью 1 – висячей, или концевой.

Пример 3.4 В показанном на рисунке графе вершина v4 является висячей: deg(v4) =1. Степени остальных вершин: deg(v1) =3; deg(v2) = deg(v3) = 2.

Если степени всех вершин графа одинаковы и равны некоторому числу k, то такой граф называется регулярным графом степени k. Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

Пример 3.5 На рисунке показаны регулярные графы соответственно степени 2 и 3.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а число входящих – полустепенью захода. Эти числа соответственно обозначаются deg(v) и deg+(v): deg(v)=deg(v) + deg+(v).








Дата добавления: 2017-06-02; просмотров: 814;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.01 сек.