Алгоритмы на графах - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритмы на графах. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Алгоритмы на графах Базовые определения. Несколько простых, но важных теорем. Способы представления в памяти.

Слайд 2

Описание слайда:

Базовые определения Рассматривают графы двух видов – ориентированные и неориентированные Ориентированный граф – это пара G(V,E), где V – произвольное непустое множество вершин, E – множество дуг, т.е. упорядоченных пар вершин (EVV). Неориентированный граф определяется аналогично, но E – множество неупорядоченных пар вершин. Элементы E называются рёбрами.

Слайд 3

Описание слайда:

Базовые определения Особые случаи дуг/рёбер: петля, кратные дуги/рёбра. Петлёй называется дуга (для неориентированного графа - ребро), соединяющая вершину с ней же. Например:

Слайд 4

Описание слайда:

Базовые определения Две дуги (ребра) называются кратными, если начальные вершины этих дуг совпадают, и конечные – тоже совпадают. Например: Допустимость петель и кратных дуг обычно оговаривается отдельно.

Слайд 5

Описание слайда:

Базовые определения Рассмотрим дугу (ребро) e=(u,v). Говорят, что дуга e инцидентна вершинам u и v. Аналогично, вершина u и вершина v инцидентны дуге e. Вершины u и v называются смежными. Дуги (рёбра), имеющие общую вершину, также называются смежными.

Слайд 6

Описание слайда:

Базовые определения Степень вершины – это количество дуг (рёбер), которым инцидентна данная вершина. Степень вершины v обозначается deg(v). Для ориентированных графов выделяют также полустепень исхода deg-(v) и полустепень захода deg+(v).

Слайд 7

Описание слайда:

Теорема Теорема 1. Для любого неориентированного графа сумма deg(v) по всем vV равна 2|V|. Следствие. На любом графе количество вершин нечетной степени четно. Аналог теоремы 1 для орграфов: Теорема 2. Для любого орграфа сумма степеней захода равна сумме степеней исхода. И эти суммы равны количеству вершин графа.

Слайд 8

Описание слайда:

Базовые определения Путём на ориентированном графе называется последовательность вершин v1, v2, …, vk, в которой для любого i вершины vi и vi+1 соединены дугой. Путь можно понимать и как последовательность дуг. Для неориентированного графа аналогичная последовательность вершин/рёбер называется цепью.

Слайд 9

Описание слайда:

Базовые определения Путь (цепь) называется простым, если в нём все вершины (за исключением, может быть, крайних) различны. Контуром (циклом) называется путь (цень), у которого начальная и конечная вершина совпадают.

Слайд 10

Описание слайда:

Теорема Теорема 3. Если в графе степень любой вершины больше или равна 2, то в этом графе существует цикл. Аналогичная теорема для ориентированных графов: Теорема 4. Если в ориентированном графе для любой вершины v deg-(v)≥0 и deg+(v) ≥0, то на данном орграфе существует контур.

Слайд 11

Описание слайда:

Способы представления графов Матрица смежности: для неориентированного графа для ориентированного графа – аналогично.

Слайд 12

Описание слайда:

Способы представления графов Матрица инцидентности: для неориентированного графа для ориентированного графа:

Слайд 13

Описание слайда:

Способы представления графов Список смежности

Слайд 14

Описание слайда:

Способы представления графов Модифицированный список смежности Два массива: A и P. В массиве A подряд записаны списки смежных вершин для всех вершин графа, в порядке нумерации. То есть массив A имеет размер |E|. В массиве P элемент p[i] равен индексу в массиве A, начиная с которого расположен список смежных вершин для vi.

Слайд 15

Описание слайда:

Рекомендуемая литература Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. – М.: Вузовская книга, 2006 г. : 268 с. Кристофидес Н. Алгоритмы на графах. — М.: Мир, 1974. Носов В.А. «Комбинаторика и теория графов», курс лекций.

Теги Алгоритмы графах

Похожие презентации