Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества. - презентация

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

2 Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества вершин и множества пар вершин.

3 Применение графов Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computer science). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т.д. Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computer science). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т.д.

4 Примеры неориентированного и ориентированного графов (А и Б)

5 Способы задания графов Явное задание графа как алгебраической системы. Явное задание графа как алгебраической системы. Геометрический Геометрический Матрица смежности Матрица смежности Матрица инцидентности Матрица инцидентности

6 Явное задание графа как алгебраической системы.. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как.. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как.

7 Геометрический способ

8 Матрица смежности

9 Матрица инцидентности

10 Маршрут Маршрут в графе – это последовательность соседних (смежных) вершин. Маршрут в графе – это последовательность соседних (смежных) вершин.

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

12 Эйлеровы и гамильтоновы циклы Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем называть эйлеровым. Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем называть эйлеровым.

13 Гамильтонов цикл Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз. Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.

14 Деревья Связный граф без циклов называется деревом. Связный граф без циклов называется деревом. Библейское генеалогическое дерево

15 Лес, листья Граф без циклов называется лесом. Вершины степени 1 в дереве называются листьями. Граф без циклов называется лесом. Вершины степени 1 в дереве называются листьями.

16 Раскраска графов Раскраской графа G = (V,E) называется отображение c: Раскраской графа G = (V,E) называется отображение c: V ® N V ® N Раскраска называется правильной, если образы любых двух смежных вершин различны: c(u) c(v), если (u,v) О I. Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа. Раскраска называется правильной, если образы любых двух смежных вершин различны: c(u) c(v), если (u,v) О I. Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа.

17 Правильная раскраска.

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

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

20