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

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

Геометрическое представление графа: вершины графа изображаются в виде точек или кружков на плоскости; если две вершины образуют ребро, то соответствующую пару точек соединяют линией.

Элементы множества E могут быть упорядоченными, если указано, какая вершина является начальной (дуги), и неупорядоченными, если ориентация не указана (ребра).

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

Ребро называется петлёй, если оно начинается и заканчивается в одной и той же вершине.

Если для вершин V , V существует ребро, их соединяющее, то говорят, что вершины V и V : а) смежные вершины, б) инцидентны ребру е.

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

Степенью вершины называется число ребер, которым эта вершина инцидентна. Обозначается deg(Vi).

Если степень вершины больше или равна трём, то вершина называется ветвящейся.

Если степень вершины равна единице, то вершина называется висячей.

Если степень вершины равна нулю, то вершина называется изолированной.

Граф, у которого каждая пара вершин соединена ребром, называется полным и обозначается K_n, где n – количество вершин. Количество рёбер полного графа равно .

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

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

Матрица смежности вершин – это квадратная матрица Р порядка n×n, где n – число вершин графа. Её стоки и столбцы соответствуют вершинам графа. Элементы матрицы смежности равны числу дуг, идущих из i- той вершины в j -тую.

В случае неориентированного графа матрица смежности будет симметричной.

Матрица инцидентности – это прямоугольная матрица R размерности n×m, где n – число вершин графа, m – число дуг (ребер). Строкам поставлены в соответствие вершины, столбцам – рёбра (дуги).

Если граф неориентированный, то элементы матрицы равны 1, если вершина инцидентна ребру , и равны 0 в противном случае.

----------------------------------------------------------------------------------------------------------------

Теория графов. Стр. 1

Для ориентированного графа элементы матрицы инцидентности равны: , если в графе имеется дуга , для которой вершина - начальная; , если в графе имеется дуга , для которой вершина - конечная, и во всех остальных случаях.

 

Операции на графах.

Объединением графов и называется граф , который содержит вершины и рёбра, которые принадлежат хотя бы одному из этих графов.

Пересечением графов и называется граф , который содержит вершины и рёбра, которые являются общими для этих графов.

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

Задачи для самостоятельного решения.

№1. Построить граф G = (V,E), где V={1;2;3;4;5}, E={(1,2); (2,3); (4;2);(4;3)}, если он: а) ориентированный; б) неориентированный.

№2. Графы и заданы матрицами смежности А и В соответственно:

, .

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

Домашнее задание.

 

№1. По матрице смежности построить геометрическое изображение графа и его матрицу инцидентности.

№2. Построить геометрическое изображение, матрицы смежности и инцидентности ориентированного графа G=(V,E), где V={v₁,v₂,v₃,v₄}, E={(v₁,v₃),(v₁,v₄),(v₂,v₃),(v₄,v₂)}.

----------------------------------------------------------------------------------------------------------------

Теория графов. Стр. 2

№3. Построить геометрические изображения , если

 

----------------------------------------------------------------------------------------------------------------

Теория графов. Стр. 3