🗊Презентация Алгоритмы на графах

Категория: Математика
Нажмите для полного просмотра!
Алгоритмы на графах, слайд №1Алгоритмы на графах, слайд №2Алгоритмы на графах, слайд №3Алгоритмы на графах, слайд №4Алгоритмы на графах, слайд №5Алгоритмы на графах, слайд №6Алгоритмы на графах, слайд №7Алгоритмы на графах, слайд №8Алгоритмы на графах, слайд №9Алгоритмы на графах, слайд №10Алгоритмы на графах, слайд №11Алгоритмы на графах, слайд №12Алгоритмы на графах, слайд №13Алгоритмы на графах, слайд №14Алгоритмы на графах, слайд №15
Скачать
Вы можете ознакомиться и скачать презентацию на тему Алгоритмы на графах. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


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

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию