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

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

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

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

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

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

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

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

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

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

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

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

Граф, у которого каждая пара вершин соединена ребром, называется полными обозначается K_n, где n – количество вершин. Количество рёбер полного графа равно Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru .

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

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

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

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

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

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

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

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

Для ориентированного графа элементы матрицы инцидентности равны: Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , если в графе имеется дуга Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , для которой вершина Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru - начальная; , если в графе имеется дуга Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , для которой вершина Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru - конечная, и во всех остальных случаях.

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

Объединением графов Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru и называется граф Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , который содержит вершины и рёбра, которые принадлежат хотя бы одному из этих графов.

Пересечением графов Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru и называется граф Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , который содержит вершины и рёбра, которые являются общими для этих графов.

Дополнением графа Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru называется граф Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , который имеет то же множество вершин, что и граф Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , а рёбра соединяют две его различные вершины только в том случае, если в исходном графе ребро между рассматриваемыми вершинами отсутствует.

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

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

№2. Графы Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru и заданы матрицами смежности А и В соответственно:

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

Необходимо построить геометрические изображения графов Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , , , , , ; построить матрицы смежности графов Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru , , , ; граф задать матрицей инцидентности; определить степени вершин графа Задачи для самостоятельного решения. Графом G называется пара множеств (V,E), где V – конечное множество, элементы которого называются вершинами - student2.ru .

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

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

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

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

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

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

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