Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Обратная связь

Презентация на тему Лекция 6. Сетевые методы и графы в автоматизированном управлении

Содержание

2. Ориентированный эйлеров графТеорема, сформулированная для неориентированных графов.
3. Ориентированный гамильтонов графСильносвязный полный ориентированный граф является гамильтоновым
4. Ациклический ориентированный графПо отношению к ациклическому ориентированному
5. Топологическая сортировкаТеорема: в ациклическом ориентированном графе имеются
6. Задание: выполнить топологическую сортировку для графа
7. Результат топологической сортировки
8. Матрица смежности ориентированного графаПусть G=(V, E) –
9. Матрица смежности неориентированного графаВ случае неориентированного графа
10. Матрицей смежности несвязного графа является нулевая матрица порядка n×n
11. Матрица достижимостей R=[rij] Все диагональные элементы в
12. Вопрос 1. Как будет выглядеть матрица достижимости
13. Матрица инциденций B=[bij] Если граф G ориентированныйЕсли
14. Построить матрицы инциденций для графов:
15. Построить матрицы инциденций для графов:
16. Свойства матриц инциденций для графов:Свойства матрицы инцидентности
17. В случае связных орграфов ранг матрицы инциденций В равен n-1.
18. Построить матрицы инциденций для графов:
19. Скачать презентацию
20. Похожие презентации

Ориентированный эйлеров графТеорема, сформулированная для неориентированных графов. Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин чётны.Для ориентированных графов преобразуется в условие такое, что для любой вершины V справедливо: d¯(V)=d+(V).

Главная
Информатика
Лекция 6. Сетевые методы и графы в автоматизированном управлении

Лекция 6 – по курсу «Сетевые методы и графы в автоматизированном управлении» Алгоритмы,формулы и рисунки

Ориентированный эйлеров графТеорема, сформулированная для неориентированных графов. Связный граф является эйлеровым тогда

Ориентированный гамильтонов графСильносвязный полный ориентированный граф является гамильтоновым

Ациклический ориентированный графПо отношению к ациклическому ориентированному графу справедливо следующее утверждение: вершины

Топологическая сортировкаТеорема: в ациклическом ориентированном графе имеются по крайней мере одна

Задание: выполнить топологическую сортировку для графа

Матрица смежности ориентированного графаПусть G=(V, E) – ориентированный граф без параллельных дуг,

Матрица смежности неориентированного графаВ случае неориентированного графа aij=1 тогда и только тогда,

Матрицей смежности несвязного графа является нулевая матрица порядка n×n

Матрица достижимостей R=[rij] Все диагональные элементы в матрице R равны 1, поскольку

Вопрос 1. Как будет выглядеть матрица достижимости для неоринтированного графа? Вопрос 2.

Матрица инциденций B=[bij] Если граф G ориентированныйЕсли граф G неориентированныйРассмотрим граф G

Построить матрицы инциденций для графов:

Свойства матриц инциденций для графов:Свойства матрицы инцидентности неориентированного графа.1. Сумма элементов матрицы

В случае связных орграфов ранг матрицы инциденций В равен n-1.

Слайды презентации

Слайд 2
Ориентированный эйлеров граф
Теорема, сформулированная для неориентированных графов. Связный

Ориентированный эйлеров графТеорема, сформулированная для неориентированных графов. Связный граф является эйлеровым

граф является эйлеровым тогда и только тогда, когда степени

всех его вершин чётны.

Для ориентированных графов преобразуется в условие такое, что для любой вершины V справедливо:

d¯(V)=d+(V).

Слайд 3
Ориентированный гамильтонов граф
Сильносвязный полный ориентированный граф является гамильтоновым

Слайд 4
Ациклический ориентированный граф

По отношению к ациклическому ориентированному графу

Ациклический ориентированный графПо отношению к ациклическому ориентированному графу справедливо следующее утверждение:

справедливо следующее утверждение:

вершины ациклического ориентированного графа G с

n вершинами

можно пометить таким образом целыми числами из множества { 1,2,…, n}, что

если в графе имеется дуга (i,j), то i < j,

т.е. каждая дуга направлена от вершины с меньшим номером к вершине с большим номером.

Такое упорядочение вершин называется топологической сортировкой.

Слайд 5 Топологическая сортировка
Теорема: в ациклическом ориентированном графе имеются по

крайней мере
одна вершина с нулевой полустепенью захода
и

одна вершина с нулевой полустепенью исхода.

Шаг 1: Выберем произвольную вершину с нулевой полустепенью исхода, пометим ее n.
Шаг 2: Удалим из графа эту вершину и инцидентные ей дуги.

Шаг 3: Получившийся граф также является ациклическим, поэтому в нем можно выбрать вершину с нулевой полустепенью исхода и пометим эту вершину n-1.

Повторим описанную процедуру до тех пор, пока не пометим все вершины.

Слайд 6
Задание: выполнить топологическую сортировку для графа

Слайд 7

Результат топологической сортировки

Слайд 8 Матрица смежности ориентированного графа
Пусть G=(V, E) – ориентированный

Матрица смежности ориентированного графаПусть G=(V, E) – ориентированный граф без параллельных

граф без параллельных дуг, в котором V={V1,V2,…,Vn}.
Сумма всех

элементов строки Vi матрицы дает полустепень исхода вершины Vi ,

а сумма элементов столбца Vi – полустепень захода вершины Vi.

Слайд 9 Матрица смежности неориентированного графа
В случае неориентированного графа aij=1

Матрица смежности неориентированного графаВ случае неориентированного графа aij=1 тогда и только

тогда и только тогда, когда существует ребро, соединяющее вершины

Vi и Vj

Сумма всех элементов строки Vi матрицы равна сумме элементов столбца Vi и равна степени вершины Vi.

Слайд 10 Матрицей смежности несвязного графа является нулевая матрица порядка

n×n

Слайд 11 Матрица достижимостей R=[rij]
Все диагональные элементы в матрице

Матрица достижимостей R=[rij] Все диагональные элементы в матрице R равны 1,

R равны 1, поскольку каждая вершина достижима из себя

самой.

Слайд 12 Вопрос 1. Как будет выглядеть матрица достижимости для

Вопрос 1. Как будет выглядеть матрица достижимости для неоринтированного графа? Вопрос

неоринтированного графа?
Вопрос 2. Как будет выглядеть матрица достижимости

для несвязного графа?

Слайд 13 Матрица инциденций B=[bij]
Если граф G ориентированный
Если граф

Матрица инциденций B=[bij] Если граф G ориентированныйЕсли граф G неориентированныйРассмотрим граф

G неориентированный
Рассмотрим граф G на n вершинах и m

ребрах

Слайд 14 Построить матрицы инциденций для графов:

Слайд 15 Построить матрицы инциденций для графов:

Слайд 16 Свойства матриц инциденций для графов:

Свойства матрицы инцидентности неориентированного

Свойства матриц инциденций для графов:Свойства матрицы инцидентности неориентированного графа.1. Сумма элементов

графа.
1. Сумма элементов матрицы на i-й строке равна степени

вершины i.
2. Сумма элементов матрицы по i-му столбцы равна 2.

Свойства матрици инцидентности орграфа.
Сумма строк матрицы B(G) является нулевой строкой.
Любая строка матрицы B(G) является линейной комбинацией остальных строк.
Ранг матрицы B(G) равен p-1.