1. Граф - это система некоторых объектов вместе с некоторыми парами этих объектов, изображающая отношения связи между ними. Графами удобно изображаются сети коммуникаций, дискретные многошаговые процессы, системы бинарных отношений, химические структурные формулы, различные схемы и диаграммы и др.
Неориентированный граф (соответственно ориентированный граф, или орграф) G - система G = (V, Е, Г),
состоящая из множества элементов V = {v}, называемых вершинами графа, множества элементов Е = {е}, называемых ребрами, и
отображения Г: Е V2, ставящего в соответствие каждому элементу е ≥ Е неупорядоченную (соответственно
упорядоченную) пару элементов v1, v2 ≥ V, называемых концами ребра е.
V U E образует множество элементов графа; при этом предполагается, что Е
V= Ø. Отображение Г определяет отношение инцидентности ребра с каждым из своих
концов. Для графа G = (V, Е, Г) употребляется также более короткое обозначение G = (V, Е) без указания инцидентностей,
которые определяются контекстом. По количеству элементов графы делятся на конечные и бесконечные. Здесь мы будем
рассматривать, в основном, конечные графы, не оговаривая этого специально.
Если Г(е) = (v1, v2) - упорядоченная пара (т.е. (v1, v2)
(v2, v1) при v1
v2), то ребро е называется ориентированной дугой, исходящей из вершины v, и входящей в вершину
v2; v1 называется началом, a v2 - концом дуги е. Если Г(е) = (v1,
v2) - неупорядоченная пара, то ребро е называется неориентированным. Всякому графу G можно поставить
в соответствие соотнесенный неориентированный граф
с теми же множествами
V и Е и инцидентностями, но все пары неупорядоченные.
Вершина, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми, или висячими. Ребро с совпадающими концами называется петлей. Две вершины, инцидентные одному и тому же ребру, называются соседними (или смежными). Два ребра, инцидентные одной и той же вершине, называются смежными. Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными, или параллельными. Для различных задач одному и тому же объекту можно сопоставить; граф по-разному. Так, фрагмент дорожной сети может быть, представлен неориентированным ребром, изображающим наличие связи между его концами (населенными пунктами, городскими площадями или перекрестками); одной или двумя дугами, передающими одностороннее или двустороннее движение транспорта; несколькими дугами - отдельно для каждого ряда движения. Ребрам могут быть, приписаны также числа, означающие длину, рядность, уклон и другие численные или иные характеристики.
2. Часто бывает важно определить, какие графы считаются различными, а какие не различаются. Обычно это связывают с понятием изоморфизма графов. Два графа G1= (V1, E1, Г1) и G2= (V2, Е2, Г2) называются изоморфными, если существуют взаимно однозначные отображения f: V1 <=> V2 и g: Е1 <=> Е2, сохраняющие инцидентность, т.е. такие, что для всякого е ≥ Е, равенство Г1(e) = (v1,v2) влечет за собой равенство Г2 (gе) = (fv1, fv2).
Во многих случаях можно рассматривать графы с точностью до изоморфизма, т.е. не различать изоморфные графы; однако, если какие-то вершины или ребра графов обладают различной индивидуальностью, например, они занумерованы или им сопоставлены какие-либо численные характеристики (вес ребра, длина ребра и др.), то естественно при сравнении двух графов эту индивидуальность учитывать.
3. Существует несколько способов задания графов, связанных с различной формой задания функции Г. Вот некоторые из них для конечных
1) Перечисление (список) ребер графа с указанием их концов и добавлением списка изолированных вершин.
2) Матрица инциденций графа с b вершинами и р ребрами - прямоугольная матрица А = ||аij|| с b строками и р столбцами, строку которой соответствуют вершинам графа, а столбцы - ребрам, причем для неориентированного графа элемент матрицы aij равен 1, если вершина Vi и ребро еj инцидентны, и равен 0 в противном случае. Для ориентированного графа аij = -1, если Vi является началом дуги еj, и аij +1, если V1 - конец дуги еj. В каждом столбце матрицы инциденций - два ненулевых элемента, если ребро - не петля. Петле соответствует элемент, равный 2.
3) Матрица соседства (смежности) вершин графа с b вершинами - квадратная матрица В =||bij|| размерности b, строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент b равен числу ребер, идущих из вершины vi в вершину Vj (bij не равно, вообще говоря, Ьji, однако для неориентированных графов матрица соседства - симметричная). Для несмежных вершин соответствующий элемент матрицы равен 0.
Если матрица инциденций задает граф однозначно, то матрица соседства вершин определяет граф с точностью до замены любого неориентированного ребра парой противоположно направленных дуг между теми же вершинами. Однако для графов без кратных ребер задание графа и этой матрицей однозначно, элементы матрицы соседства равны в этом случае 0 или 1.
4) Для наглядности граф часто представляют в виде геометрического объекта: вершинам соответствуют различные выделенные точки в пространстве (на плоскости), ребрам - отрезки кривых, связывающие соответствующие точки и не проходящие через выделенные точки, отличные от их концов. Отношению инцидентности вершин и ребер графа соответствует при этом геометрическая инцидентность выделенных точек и линий. Кроме того, предполагается, что кривые попарно не пересекаются во внутренних точках. Такое представление графа называется реализацией.
Можно показать, что всякий граф с конечным (и даже счетным) числом элементов может быть реализован в трехмерном пространстве, причем, если граф не содержит кратных ребер, то ребра можно реализовать прямолинейными отрезками. На плоскости реализуется не всякий граф, что порождает разделение графов на плоские и неплоские. Тем не менее даже неплоский граф бывает удобно изображать на плоскости, надо только отличать вершины от пересечений ребер на рисунке (например, изображать вершины кружками); ориентацию ребер показывают стрелками.
Если представить графом уличную (дорожную) сеть, где ребра изображают отрезки дорог, связывающие соседние вершины (площади и перекрестки), то для небольшого населенного пункта такой граф может быть плоским, но для города с путепроводами, мостами и транспортными развязками в разных уровнях, он скорее всего неплоский.
На рисунке 1 изображен граф с 8 вершинами и 11 ребрами и проиллюстрированы некоторые введенные понятия: ребра е1,е3,е6, e7, e9, e10 являются дугами; v6 - изолированная вершина; е4 и е5 -параллельные ребра; е6 е7, е8, е9 - также параллельные ребра, е11 -петля; v2 и v3, v2 и v4 - пары соседних вершин; е3 и е4 - пара смежных ребер. Матрица инциденций А и матрица соседства вершин В этого графа таковы:
A= | ![]() |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ![]() |
-1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 0 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | 0 | 0 | |||
0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | -1 | 0 | 0 | |||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | |||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 |
B= | ![]() |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ![]() |
1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |||
0 | 1 | 0 | 2 | 0 | 0 | 0 | 0 | |||
0 | 1 | 2 | 0 | 3 | 0 | 0 | 0 | |||
0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | |||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 0 | 0 | 0 | 0 | 0 | 2 | 1 | |||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4. Рассмотрим несколько примеров графов, имеющих интересные применения.
(1)Полным графом называется граф без кратных ребер (и иногда без петель), в котором любые две вершины соединены ребром (ориентированным или неориентированным). Полный неориентированный граф с b вершинами обозначается Кb. Очевидно, граф Кb содержит Сb2 = b * (b - 1) / 2 ребер. Полный ориентированный граф иногда называют турниром, поскольку он отражает результат состязания по круговой системе в один круг. Полный граф представляет бинарное отношение R: если R рефлексивно, то граф - с петлями; если R симметрично, то граф - неориентированный, если R антисимметрично, то - ориентированный.
На рисунке 2 а, б, в изображены графы К3, К4, К5. На рисунке 2 г граф К5 представлен с минимальным числом пересечений изображений ребер: устранить их полностью нельзя.
![]() | ![]() | ![]() | ![]() |
a | б | в | г |
Рисунок 2 |
(2) Двудольным графом называется граф, вершины которого разбиты на два непересекающихся класса: V = V1, U V2, а ребра связывают вершины только из разных классов - не обязательно все пары (рисунок 3). Если же каждая из вершин класса V, связана ребром с каждой вершиной класса V2, то граф называется полным двудольным и обозначается Km,n, где m = |V1, |, n = | V2|. Очевидно, граф Km,n содержит (m+n) вершин и m ∙ n ребер. На рисунке З а изображен двудольный граф, на рисунке 3 6, в - полные двудольные графы К32 и К33 (последний носит название "3 дома - 3 колодца"). Упражнение. Изобразите граф К33 с минимально возможным числом пересечений.
![]() |
![]() |
![]() |
a | б | в |
Рисунок 3 |
(3) n-мерным единичным кубом называется граф Еn, вершинами которого являются все наборы длины n из нулей и единиц, а ребра соединяют вершины, различающиеся ровно в одной компоненте. Случаи n = 3 и n = 4 представлены на рисунке 4 а, б.
![]() |
![]() |
a | б |
Рисунок 4 |
Упражнение. Докажите, что графы Еn являются двудольными (указание: рассмотрите наборы с различным числом единиц).
5. Граф Н = (V', Е') называется подграфом графа G = (V, Е), обозначение: Н G, если V'
V, Е'
Е и для множеств V' и Е' сохраняются инциденции графа G. При этом, очевидно, каждое ребро из Е' входит в подграф Н вместе со своими концами.
Иногда рассматриваются только подграфы без изолированных вершин или только подграфы, содержащие все вершины графа (и только часть ребер); такие подграфы полностью определяются множеством своих ребер. В этих случаях можно естественным образом определить теоретико-множественные операции над подграфами: пересечение, объединение, симметрическую разность (называемую также суммой по модулю 2 или просто суммой), дополнение до всего графа. Подграфом, натянутым на множество вершин V' V графа G, называется подграф, содержащий вершины из V и все ребра графа G, соединяющие пары вершин из V'.
Подграф Z , состоящий из всех ребер, инцидентных вершине а, называется звездой вершины
. Для графов без петель степень s(
) вершины
есть число ребер в звезде Z
. Очевидно, что сумма степеней всех вершин графа без петель равна удвоенному числу ребер.
Для графа, изображенного на рисунке 1, s(v1) = 1, s(v2) = s(v3) = 3, s(v4)= 7,s(v6) = 0.
Если все вершины графа имеют одинаковую степень s (такой граф называют однородным), то сумма степеней его вершин равна b ∙ s, а число ребер равно b ∙ s / 2.
Упражнение. Определите число ребер в графах Е3, Е4 (рисунок 4а, б).
В неориентированном графе сумма степеней всех вершин равна удвоенному числу ребер m графа, т.е. четна.
Петля дает вклад 2 в степень вершины.
Отсюда следует, что в неориентированном графе число вершин нечетной степени четно.
Для вершин орграфа определяются две локальные степени:
Петля дает вклад 1 в обе эти степени.
В орграфе суммы степеней всех вершин ρ1(ν) и ρ2(ν) равны количеству ребер m этого графа, а значит, и равны между собой.
Если степень вершины равна 0, т.е. d(ν)=0, то вершина называется изолированной. Если степень вершины равна 1, d(ν)=1, то вершина называется концевой или висячей.
Для орграфа число дуг, исходящих из вершины ν, называются полустепенью исхода, а а входящих - полустепенью захода. Обозначается так: d-(ν) и d+(ν).
Теорема Эйлера.
Сумма степеней вершин графа равна удвоенному количеству ребер.
Множество вершин графа называется независимым (внутренне устойчивым), если никакие две вершины из этого множества не смежны. Независимое множество вершин называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности из максимальных независимых множеств называется наибольшим. Число вершин в наибольшем независимом множестве графа G называется числом независимости (числом внутренней устойчивости, неплотностью) и обозначается через α0(G).
На рисунке 5 показан граф G, у которого число независимости α0(G)=4. Множество вершин {ν1,ν2,ν3,ν7}; {ν1,ν2,ν3,ν8}; {ν2,ν3,ν5,ν7}; {ν2,ν3,ν5,ν8} являются наибольшими независимыми множествами. Множество вершин {ν4,ν7} является максимальным независимым множеством, но не наибольшим.
Произвольное подмножество попарных несмежных ребер графа называется паросочетанием (независимым множеством ребер). Паросочетание графа G называется максимальным, если оно не содержится в паросочетании с большим числом ребер. Паросочетание является наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа G. Число ребер в наибольшем паросочетании называется числом паросочетаний и обозначается через α1(G).
Независимые множества ребер графа G находятся во взаимно однозначном соответствии с независимым множеством вершин реберного графа L(G), т.е. α1(G)=α0((L)G)).
![]() | Практические задания |
![]() | Tест для самоконтроля |