Теория графов
Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 14.05.2012 |
| Размер файла | 225,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Теория графов
Основные понятия и определения
Граф - пара множеств V и X - G = (V, X). V - множество вершин, X - множество ребер.
Петля - ребро вида (v, v).
Кратные рёбра - одинаковые пары в X.
Ориентированный граф (орграф D) - граф, для которого пары в Х упорядочены. Ребра в орграфе называются дугами и обозначаются <u, v>.
Степенью вершины V графа G называется число (v) рёбер графа, инцидентных вершине v. Если (v) = 1, тогда v - висячая вершина, если (v) = 0, тогда v - изолированная вершина.
Полустепенью исхода (захода) вершины v орграфа D называется +(v) - число дуг, исходящих из v (д - (v) - число дуг, заходящих в v).
Маршрутом для графа G (путём для орграфа D) называется последовательность v1x1v2x2v3…xkvk+1.
Цепь - незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.
Простая цепь - цепь, в которой все вершины попарно различны.
Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.
Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.
Длина пути - число рёбер (дуг) в маршруте (пути).
Путь в графе называется минимальным, если он состоит из минимального количества рёбер.
Орграф D называется нагруженным, если на множестве дуг Х определена весовая функция - длина дуги хХ.
Путь называется минимальным в нагруженном графе или орграфе, если он имеет минимальную длину пути.
Матрица смежности (графа, орграфа): А = [aij], V = {v1…, vn},
X = {x1…, xm}
Матрица инцидентности: B = [bij]
(орграфа D)
(графа G)
Матрица достижимости T = [tij]
Матрица связности S = [sij]
(орграфа D)
(графа G)
Дерево - связный граф без циклов
Остовное дерево графа (ОД) - любой связный подграф связного графа, содержащий все вершины и являющийся деревом.
Минимальное остовное дерево (МОД) - остовное дерево нагруженного графа с минимальной суммой длин дуг, содержащихся в нём.
Цикломатическое число связного графа G (число циклов в базисе циклов графа) , где n - количество вершин, m - количество ребер в графе.
Ориентированный граф
Назовем ребра графа:
1. Характеристика графа
Ориентированный псевдограф D=(V, X).
V={V0, V1, V2, V3, V4, V5}; X={X0, X1, X2, X3, X4, X5, X6, X7}
X0=<V2, V1>, X1=<V0, V3>, X2=<V0, V3>, X3=<V0, V1>, X4=<V0, V2>, X5=<V4, V0>, X6=<V3, V4>, X7=<V4, V4>
2. Специальные вершины и ребра
X7 - петля, X1, X2 - кратные ребра, V5 - висячая вершина
3. Полустепени вершин
+(V) - число дуг, заходящих в V
д - (V) - число дуг, исходящих из V
д+ (V0)=1 д+ (V1)=2 д+ (V2)=1 д+ (V3)=2 д+ (V4)=2 д+ (V5)=0
дЇ(V0)=4 дЇ(V1)=0 дЇ(V2)=1 дЇ(V3)=1 дЇ(V4)=2 дЇ(V5)=0
4. Матрицы смежности, инцидентности, достижимости, связности
|
Смежности |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
|
|
V0 |
0 |
1 |
1 |
2 |
0 |
0 |
|
|
V1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
V2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
V3 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
V4 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
V5 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Инцидентности |
X0 |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
|
V0 |
0 |
-1 |
-1 |
-1 |
-1 |
1 |
0 |
0 |
|
|
V1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
V2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
V3 |
0 |
1 |
1 |
0 |
0 |
0 |
-1 |
0 |
|
|
V4 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
±1 |
|
|
V5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Достижимости |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
|
|
V0 |
1 |
1 |
1 |
1 |
0 |
0 |
|
|
V1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
V2 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
V3 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
V4 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
V5 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Связности |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
|
|
V0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
V1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
V2 |
0 |
0 |
1 |
0 |
0 |
||
|
V3 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
V4 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
V5 |
0 |
0 |
0 |
0 |
0 |
1 |
5. Цикл, цепь, простой цикл, простая цепь
Простой цикл: V0 X1 V3 X6 V4 X5 V0 Цикл: V3 X6 V4 X7 V4 X5 V0 X2 V3
Простая цепь: V0 X4 V2 X0 V1 Цепь: V0 X1 V3 X6 V4 X5 V0 X4 V2 X0 V1
Неориентированный граф
1. Начертить граф
2. Характеристика графа
Неориентированный граф G=(V, X)
V={V0, V1, V2, V3, V4, V5, V6}
X={X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11}
X0={V0, V1}, X1={V0, V2}, X2={V0, V3}, X3={V2, V4}, X4={V1, V4}, X5={V1, V2}, X6={V2, V3}, X7={V4, V5}, X8={V3, V5}, X9={V2, V5}, X10={V4, V6}, X11={V5, V6}
3. Специальные вершины и ребра
Нет
4. Степени вершин
д(V0)=3 д(V1)=3 д(V2)=5 д(V3)=3 д(V4)=4 д(V5)=4 д(V6)=2
5. Матрицы смежности, инцидентности, достижимости, связности
|
Смежности |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
|
|
V0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
V1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
V2 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
|
V3 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
V4 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
V5 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
V6 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
Инцидентности |
X0 |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
|
V0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
V1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
V2 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
V3 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
V4 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
V5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
V6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
Достижимости |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
|
|
V0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V3 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V4 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
Связности |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
|
|
V0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V3 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V4 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
V6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
6. Цикл, цепь, простой цикл, простая цепь
Простой цикл: V0 X2 V3 X6 V2 X1 V0 Цикл: V0 X0 V1 X4 V4 X10 V6 X11 V5 X9 V2 X1 V0
Простая цепь: V4 X7 V5 X8 V3 Цепь: V4 X10 V6 X11 V5 X9 V2
7. Числовые характеристики графа
a) Максимальное удаление - r(V) = maxwd (V, W)
r(V0)=6, r(V1)=6, r(V2)=6, r(V3)=6, r(V4)=6, r(V5)=6, r(V6)=6
б) Диаметр графа d(G)=maxv,wd (v, w)
d(G)=6
в) Радиус графа G - r(G)=minv r(V)
R(G)=6
г) Центры графа-V| R(G)=r(V)
центры графа - вершины V0, V1, V2, V3, V4, V5, V6
8. Остовное дерево и минимальное оставное дерево
Рассчитаем остовное дерево графа:
Рассчитаем минимальное остовное дерево графа:
9. Обход графа в глубину и в ширину
Обход графа в глубину: V0V1V2V3V5V4V6
Обход графа в ширину. 1 ярус: V0; 2 ярус: V1, V2, V3; 3 ярус: V4, V5; 4 ярус: V6
10. Базис циклов графа
Чтобы найти базис циклов графа, к остовному дереву будем добавлять по одному ребра, которые в остовное дерево не вошли. При этом на каждом шаге будем получать один простой цикл.
граф определенный матрица смежность
Добавим ребро X2 Добавим ребро X3
Получим цикл 1: V0 X1 V2 X6 V3 X2 V0 Получим цикл 2: V0 X1 V2 X3 V4 X4 V1 X0 V0
Добавим ребро X5 Добавим ребро X7
Получим цикл 3: V1 X5 V2 X1 V0 X0 V1 Получим цикл 4: V4 X7 V5 X8 V3 X6 V2 X3 V4
Добавим ребро X9 Добавим ребро X11
Получим цикл 5: V2 X6 V3 X8 V5 X9 V2 Получим цикл 6: V4 X7 V5 X11 V6 X10 V4
Размещено на Allbest.ru
Подобные документы
Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Понятие матрицы достижимости и связности. Операция удаления вершины из графа. Алгоритм выделения компонент сильной связности. Разработка и листинг программы на языке Turbo Pascal, осуществляющей вычисление матрицы достижимости по заданному алгоритму.
курсовая работа [584,3 K], добавлен 26.04.2011История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
курсовая работа [271,1 K], добавлен 09.05.2015Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011
