Самостоятельная работа по предмету: дискретные структуры графы. Основные определия. Способы задания. Понятие связанного и полного графа

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММЕДА АЛЬ-ХОРЕЗМИ
САМОСТОЯТЕЛЬНАЯ РАБОТА
ПО ПРЕДМЕТУ:
ДИСКРЕТНЫЕ СТРУКТУРЫ
ГРАФЫ. ОСНОВНЫЕ ОПРЕДЕЛИЯ. СПОСОБЫ ЗАДАНИЯ. ПОНЯТИЕ СВЯЗАННОГО И ПОЛНОГО ГРАФА

ВЫПОЛНИЛ: МАМАРАХИМОВ А. Н.

ПРОВЕРИЛ: САБИРОВ К. К.
ГРАФЫ. ОСНОВНЫЕ ОПРЕДЕЛИЯ. СПОСОБЫ ЗАДАНИЯ. ПОНЯТИЕ СВЯЗАННОГО И ПОЛНОГО ГРАФА

ГРАФ
Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Граф G=(V, Е) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами. Каждое ребро определяется парой вершин. Если ребра графа определяются упорядоченными парами вершин, то G называется направленным или Ориентированным графом. В противном случае G называется ненаправленным или Неориентированным графом. Для обозначения вершин графа будем использовать символы v1, v2, v3,…, а для обозначения ребер - е1, е2, е3, . . . . Вершины vi и vj, определяющие ребро ei, называются концевыми вершинами ребра еi. В этом случае ребро еi обозначается как ei=(vi, vj). Заметим, что в множестве Е допускается более чем одно ребро с одинаковыми концевыми вершинами. Все ребра с одинаковыми концевыми вершинами называются параллельными. Кроме того, концевые вершины ребра не обязательно различны. Если еi= (vi, vi), то ребро ei называется петлей. Граф называется простым, если он не содержит петель и параллельных ребер. Граф G является графом порядка n, если множество его вершин состоит из n элементов.

Граф, не имеющий ребер, называется Пустым. Граф, не имеющий вершин (и, следовательно, ребер), называется Нуль-графом.

Графически граф может быть представлен диаграммой, в которой вершина изображена точкой или кружком, а ребро — отрезком линии, соединяющим точки или кружки, соответствующие концевым вершинам ребра. Например, если V={v1 v2, v3, v4, v5, v6} и E= {e1, e2, e3, e4, e5}, такие, что e1=(v1, v2), e2=(v1, v4), e3= (v5, v6), e4= (v1, v2), e5=(v5,v5), тогда граф G=(V, E) представляется так, как изображено на рис. 1. В этом графе е1 и e4 - параллельные ребра, е5 - петля. Говорят, что ребро Инцидентно своим концевым вершинам. Две вершины Смежны, если они являются концевыми вершинами некоторого ребра. Если два ребра имеют общую концевую вершину, они называются Смежными.

Рис.1
Например, в графе на рис. 1 ребро е1 инцидентно вершинам v1 и v2; v1 и v4 являются смежными вершинами, а е1 и е2 - смежными ребрами.

Число инцидентных вершине vi ребер называется степенью вершины и обозначается d(vi). Иногда степень вершины называется также ее валентностью. Вершина степени 1 называется Висячей вершиной. Единственное ребро, инцидентное висячей вершине, называется висячим. Вершина степени 0 называется Изолированной. По определению петля при вершине vi добавляет 2 в степень соответствующей вершины. Величины δ(G) и ∆(G) обозначают минимальную и максимальную степени вершины в G соответственно.

В графе G на рис. 1 d(v1) = 3, d(v2) = 2, d(v3) = 0, d (v4) = 1, d (v5) = 3, d(v6) = 1.

Заметим, что v3- изолированная вершина, v4 и v6- висячие вершины, е2 — висячее ребро. Легко проверить, что сумма степеней вершин в данном графе G равна 10, тогда как число ребер равно 5. Таким образом, сумма степеней вершин графа G равна удвоенному числу ребер графа G и, следовательно, является четным числом. Более того, можно показать, что число вершин графа G нечетной степени также четно. Эти результаты свойственны не только графу на рис. 1.

СПОСОБЫ ЗАДАНИЯ.

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

Рис. 2
Другое задание графа - списком. Можно считать, что в соответствии с теоретико-множественным определением графа все элементы множества R⊆V×V, входящего в определение, т. е. упорядоченные пары, упорядочены сначала по первым элементам пар, а затем по вторым, в соответствии с нумерацией вершин (нумерацией элементов множества V). Тогда два представления графа с рис.2 будут заданы двумя списками (рис. 3):


Рис. 3
В первом столбце - первые элементы пар, затем по строкам, списком через запятую, идут вторые элементы.

Третье задание графа - матрицами. Ниже выписаны две матрицы - A и B, задающие два представления графа с рис. 2:

Рис. 4

ПОНЯТИЕ СВЯЗАННОГО И ПОЛНОГО ГРАФА

Определения

1) Вершины a и b графа G называются связанными, если в графе существует путь между ними.
2) Граф называется связным, если любые две его вершины связаны.
3) Очевидно, связанность вершин — отношение эквивалентности, и все вершины графа по этому отношению разбиваются на классы эквивалентности — множества попарно связанных вершин. Эти классы эквивалентности мы будем называть компонентами связности графа G. 4) Множество U ⊂ V (G) называется связным, если граф G(U) связен. Таким образом, компонента связности — это максимальное по включению связное множество вершин графа. Часто под компонентами связности графа G подразумевают максимальные связные подграфы этого графа, то есть, индуцированные подграфы на компонентах связности в смысле нашего определения.
Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром. В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Для задания полного графа достаточно знать число его вершин. Полный граф с  вершинами обычно обозначается через  .
Граф, не являющийся полным, можно преобразовать в полный с теми же вершинами, добавив недостающие ребра. Вершины графа  и ребра, которые добавлены, тоже образуют граф. Такой граф называют дополнением графа  и обозначают его  .