Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I. Цели и задачи освоения дисциплины
  2. I. Цель и задачи преддипломной практики.
  3. II Всероссийский Съезд Советов рабочих и солдатских депутатов и его решения.
  4. II. Задачи и направления деятельности методического объединения
  5. II. Цели и задачи выпускной квалификационной работы
  6. II. ЦЕЛИ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ
  7. II. Цели и задачи службы
  8. II. Цели и задачи фестиваля
  9. II. Цель, задачи и основа Стратегии
  10. V2: Предмет, задачи, метод патофизиологии. Общая нозология.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

 

Построение остовного дерева минимальной длины.

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

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

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

Цепь, в которой первая и последняя вершины совпадают, называется циклом.

Граф называется связным, если любые две его вершины соединены простой цепью.

Связный граф, не содержащий циклов, называется деревом.

Граф, не имеющий циклов, называется лесом.

Граф, который не имеет ни одного ребра, называется пустым.

Граф H называется подграфом графа G, если вершины и рёбра H принадлежат G.

Подграф графа G, содержащий все вершины графа называется остовным. Если остовный подграф является деревом, то он называется остовным деревом.

Если каждому ребру (дуге) графа поставлено в соответствие некоторое число , то граф G называется графом со взвешенными рёбрами (дугами). Число называется весом ребра (дуги).

Алгоритм Краскала.

1. К пустому графу прибавим ребро минимальной длины. Получим граф .

2. пусть построен граф . Граф , где ребро не принадлежит графу и не образует цикла с рёбрами графа .

3. - искомое дерево.

Алгоритм Прима.

1. Выберите произвольную вершину и ребро, соединяющее её с ближайшим (по весу) соседом.

2. Найдите не присоединённую (ещё) вершину, ближе всего лежащую к одно из присоединённых, и соедините с ней.

3. Повторяйте шаг 2 до тех пор, пока все вершины не будут присоединены.

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

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

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

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

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

, .

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

№3. Для графа G, заданного матрицей весов, построить остовное дерево минимальной длины и найти его вес:

а) ; б) .

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

 

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

, .

Необходимо:

1) построить геометрические изображения графов и ;

2) построить геометрическое изображение объединения графов и , а также матрицу смежности полученного графа;

3) построить геометрическое изображение пересечения графов и , а также матрицу смежности полученного графа;

4) граф задать матрицей инцидентности;

5) определить степени вершин графа ;

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

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

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




Дата добавления: 2015-04-11; просмотров: 34 | Поможем написать вашу работу | Нарушение авторских прав

<== 1 ==> |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав