Презентация Графы. Основные определения, способы задания онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Графы. Основные определения, способы задания абсолютно бесплатно. Урок-презентация на эту тему содержит всего 31 слайд. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:31 слайд
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.15 MB
- Просмотров:88
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Дискретная математика
Графы.
Основные определения, способы задания
№2 слайд
Содержание слайда: Определение графа
Пусть V – множество вершин,
а Е – множество ребер.
Графом G называется пара объектов (V, E) между которыми задано отношение инцидентности:
Г : е → (v, w),
где вершина v и ребро e инцидентны друг другу, если вершина является для этого ребра концевой точкой.
№3 слайд
Содержание слайда: Определение графа
Вершины v' и v" называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны одному и тому же ребру.
Ребра e' и e" называются смежными, если они имеют, по крайней мере, одну общую вершину (инцидентны одной вершине).
№4 слайд
Содержание слайда: Определение графа
Граф, содержащий направленные ребра (дуги) с началом v' и концом v" , называется ориентированным графом (орграфом). Для орграфа
Граф, содержащий ненаправленные ребра с конами v' и v" , называется неориентированным графом (нрграфом). Для нрграфа
№5 слайд
Содержание слайда: Определение графа
Рис.1 Неориентированное ребро (a,b)
Рис.2 Ориентированное ребро (a,b)
№6 слайд
Содержание слайда: Определение графа
Ребро, концевые вершины которого совпадают, называется петлей.
Рис.3.
Неориентированная
петля
Рис.4. Ориентированная
петля
№7 слайд
Содержание слайда: Определение графа
Ребра (дуги), имеющие одинаковые начало и конец, называются параллельными или кратными.
Рис.5 Кратные неориентированные ребра
№8 слайд
Содержание слайда: Определение графа
Рис. 6. Кратные ориентированные ребра
№9 слайд
Содержание слайда: Определение графа
Ребра орграфа, соединяющие одну и туже пару вершин в разных направлениях называются симметричными или противоположнонаправленными.
Рис. 7. Симметричные ребра
№10 слайд
Содержание слайда: Определение графа
Граф называется конечным, если множество его элементов (вершин и ребер) конечно.
Рис. 8. Конечный граф
№11 слайд
Содержание слайда: Определение графа
Граф называется бесконечным, если бесконечно множество вершин или множество его ребер.
Рис. 9. Граф с бесконечным числом вершин
№12 слайд
Содержание слайда: Определение графа
Рис. 10. Граф с бесконечным числом ребер
№13 слайд
Содержание слайда: Определение графа
Рис. 11. Бесконечный граф
№14 слайд
Содержание слайда: Каноническое соответствие
Каждому неориентированному графу канонически соответствует ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющим противоположные направления.
№15 слайд
Содержание слайда: Каноническое соответствие
Рис 12. Канонически соответствующие графы
№16 слайд
Содержание слайда: Способы задания
Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности.
Пусть вершины графа ;
ребра графа G.
Граф задают:
1) Матрицей инцидентности
2) Матрицу смежности
3) Списком ребер
3) Рисунком
№17 слайд
Содержание слайда: Матрица инцидентности
матрица инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой
для нграфа
№18 слайд
Содержание слайда: Матрица инцидентности
для орграфа
№19 слайд
Содержание слайда: Пример: матрица инцидентности н-графа
№20 слайд
Содержание слайда: Пример: матрица инцидентности ор-графа
№21 слайд
Содержание слайда: Матрица смежности
Матрица смежности
размера , столбцам и строкам которой соответствуют вершины графа.
Для нграфа равно количеству ребер, связывающих i-ю и j-ю вершины,
для орграфа равно количеству ребер выходящих из i-й и входящих в j-ю вершину.
№22 слайд
Содержание слайда: Матрица смежности
Матрица смежности нграфа всегда симметрична.
Матрица смежности орграфа в общем случае не симметрична.
Она симметрична, если данному орграфу есть канонически соответсвующий нграф.
№23 слайд
Содержание слайда: Пример: матрица смежности н-графа
№24 слайд
Содержание слайда: Пример: матрица смежности ор-графа
№25 слайд
Содержание слайда: Список ребер
Списком ребер можно задать граф без кратных ребер.
Ребро представляется парой вершин, инцидентных ему, например е =(v, w).
Для н-графа порядок вершин в строке произволен, для ор-графа первым стоит номер вершины–начала ребра.
№26 слайд
Содержание слайда: Рисунок
Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам – линии на плоскости, причем, линия соединяет только те точки, которые соответствуют вершинам, инцидентным данной линии-ребру.
Граф для которого возможна геометрическая интерпретация на плоскости, называется планарным.
№27 слайд
Содержание слайда: Пример: список ребер н-графа
E={(a,a), (a,b), (a,c), (b,c)}
№28 слайд
Содержание слайда: Пример: список ребер ор-графа
E={(a,a), (a,b), (a,c), (с,a), (b,c)}
№29 слайд
Содержание слайда: Планарные графы
На рисунке приведен пример не планарного графа
Рис. 12 Граф «три дома - три колодца»
№30 слайд
Содержание слайда: Изоморфные графы
Графы, отличающиеся только нумерацией вершин, называются изоморфными.
№31 слайд
Содержание слайда: Изоморфные графы
Рис.13. Изоморфные графы
Скачать все slide презентации Графы. Основные определения, способы задания одним архивом:
