Лекция по теме "Графы в дискретной математике"

1. Основные понятия и определения

Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёнинг.
Но первая работа по теории графов принадлежала Леонарду Эйлеру и была написана еще в 1736 г.
С помощью графов изображаются:
схемы различных дорог,
линии воздушных сообщений,
газопроводов,
теплотрасс,
электросетей,
микросхемы,
дискретные многошаговые процессы,
системы различных бинарных отношений,
химические структурные формулы
другие диаграммы и схемы.
Без графов сложно анализировать классификации в различных науках.

Графом G = (V, X) называется

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

Дан граф G=(V,X), где V={V,W,…} – конечное непустое множество его вершин, а X(V,W) – его ребра.
Если ребро графа G соединяет две его вершины V и W то говорят, что это ребро им инцидентно.
Две вершины графа называются смежными, если существует инцидентное им ребро: на рисунке а) смежные вершины - A и B, A и C.
Если граф G имеет ребро X(V,V), у которого начало и конец совпадают, то это ребро называется петлей. На рисунке г) петля – q(C,C).
Два ребра называются смежными, если они имеют общую вершину. На рисунке в) смежными являются, например, ребра х1 и х2 с общей вершиной С.

Граф G(V,X) может иметь ребра с одинаковыми парами вида X(V,W). Такие ребра называются кратными, или параллельными ( а) x1(A,B),x2(A,B) - кратные ребра)
Количество одинаковых пар вида x(V,W) называется кратностью ребра (V,W).
На рисунке а) ребро АС имеет кратность, равную 3, а ребро АВ – кратность, равную 2.
Число ребер, инцидентных вершине А, называется степенью этой вершины и обозначается deg(A).
Если вершине инцидента петля, она дает вклад в степень, равный двум, так как оба конца приходят в эту вершину.

На рисунке в), вершина А имеет степень, равную 1, С- 4 вершина D- 2.
Записывается это в виде: deg(A)=1, deg(C)=4, deg(D)=2.
Граф G4 рисунок г) содержит четыре вершины V={A, B, C, D} и шесть ребер : deg(A)=3, deg(В)=3, deg(C)=3, deg(D)=2.

2. Типы графов

Вершина графа, имеющая степень, равную нулю, называется изолированной.
Граф, состоящий из изолированных вершин, называется нуль-графом. Для нуль-графа Х= .
Вершина графа, имеющая степень, равную 1, называется висячей на рисунке г, вершина Е – изолированная: deg(E)=0, а вершины A, B,E, G, H на рисунке в) – висячие.
Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Полным является граф G2 на рисунке б).

Дополнением графа G(V, X) называется граф (V, X) с теми же вершинами V, что и граф G, и имеющий те и только те ребра Х’ , которые необходимо добавить к графу G, чтобы он стал полным. Например, дополнением графа G5 до графа G2 на рис. б) является граф 5
Дополнением полного графа будет нуль-граф, и наоборот.

Тема 3.2 Различные графы

Если все пары (Vh Vj) во множестве X являются упорядоченными, т. е. кортежами длины 2, то граф называется ориентированным, орграфом, или направленным.
В таком случае ребра принято изображать стрелками.

Началом ребра называется вершина, указанная в кортеже первой, концом — вторая вершина этой пары (графически она указана стрелкой).
Ребра ориентированного графа имеют называются дугами. Очевидно, дуги (V1 , V3) и (V3, V1), если они обе существуют, различны: (V1 , V3)  (V3, V1).

Блок-схема — это ориентированный граф, указывающий порядок исполнения команд алгоритма.
Вершины такого графа могут быть одного из трех типов:
функциональная вершина (F);
предикатная вершина (Р), (t, т.е. true, означает «истина», f, т.е. false, — «ложь»);
объединяющая вершина (вершина «слияния») (U).

Иногда вместо t пишут «да» (либо знак «+»), вместо f— «нет» (либо знак «-»).

Последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом.
Число ребер маршрута называется длиной маршрута. Например, в HCDFD — маршрут длиной 4. Обозначение: |HCDFD| = 4.

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины (а, следовательно, и ребра), кроме, возможно, крайних, различны. Маршрут называется циклическим, если V1=VL+1 (замкнутый маршрут).
Циклическая цепь называется циклом, а циклическая, простая цепь – простым циклом (все его n вершин различны). Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом (цепью или простой цепью).
Длина всякого простого цикла не менее трех, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом, обозначается g(G). Окружение графа G (обозначается с(G)) – длина самого длинного простого цикла графа G. Эти понятия не определены, если в G нет циклов.

Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом. В графе G4:
(t, s, р, r), (и, s, t, r) — циклы длиной 4, (r, t, q, s, и) — цикл длиной 5,
(t, s, и, r, t, s, р, r) — 8-цикл,
(р,и) — 2-цикл, петля (q) — 1-цикл.
Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами. Обозначается как d( V1, V2) (от лат. distantio — расстояние) d( V1, V2) = min|V,...V2|.

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

Ребро (V, W) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа (G’ и G”). На рис. мост (СЕ) разделил связный граф G, на два различных связных графа: G’ с вершинами (A,B,C,D) и G” с вершинами (Е, F, G, Н, I). Также мостом является ребро ВС.

Графы G8’ и G8” называются изоморфными,

если существует взаимно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вершины

Граф G называется планарным (плоским), если существует изоморфный ему граф G’, в изображении которого на плоскости ребра пересекаются только в вершинах.
Иными словами, у планарного графа никакие два ребра не имеют общих точек, кроме общих вершин. На рис. графы G1 и G3 являются планарными, а G2 — нет.