🗊Презентация Графы. Основные определения, способы задания

Категория: Математика
Нажмите для полного просмотра!
Графы. Основные определения, способы задания, слайд №1Графы. Основные определения, способы задания, слайд №2Графы. Основные определения, способы задания, слайд №3Графы. Основные определения, способы задания, слайд №4Графы. Основные определения, способы задания, слайд №5Графы. Основные определения, способы задания, слайд №6Графы. Основные определения, способы задания, слайд №7Графы. Основные определения, способы задания, слайд №8Графы. Основные определения, способы задания, слайд №9Графы. Основные определения, способы задания, слайд №10Графы. Основные определения, способы задания, слайд №11Графы. Основные определения, способы задания, слайд №12Графы. Основные определения, способы задания, слайд №13Графы. Основные определения, способы задания, слайд №14Графы. Основные определения, способы задания, слайд №15Графы. Основные определения, способы задания, слайд №16Графы. Основные определения, способы задания, слайд №17Графы. Основные определения, способы задания, слайд №18Графы. Основные определения, способы задания, слайд №19Графы. Основные определения, способы задания, слайд №20Графы. Основные определения, способы задания, слайд №21Графы. Основные определения, способы задания, слайд №22Графы. Основные определения, способы задания, слайд №23Графы. Основные определения, способы задания, слайд №24Графы. Основные определения, способы задания, слайд №25Графы. Основные определения, способы задания, слайд №26Графы. Основные определения, способы задания, слайд №27Графы. Основные определения, способы задания, слайд №28Графы. Основные определения, способы задания, слайд №29Графы. Основные определения, способы задания, слайд №30Графы. Основные определения, способы задания, слайд №31
Скачать

Содержание ▲

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

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

Слайд 1


Дискретная математика Графы. Основные определения, способы задания
Описание слайда:
Дискретная математика Графы. Основные определения, способы задания

Слайд 2


Определение графа Пусть V – множество вершин, а Е – множество ребер. Графом G называется пара объектов (V, E) между которыми задано отношение инцидентности: Г : е → (v, w), где вершина v и ребро e инцидентны друг другу, если вершина является для этого ребра концевой точкой.
Описание слайда:
Определение графа Пусть V – множество вершин, а Е – множество ребер. Графом G называется пара объектов (V, E) между которыми задано отношение инцидентности: Г : е → (v, w), где вершина v и ребро e инцидентны друг другу, если вершина является для этого ребра концевой точкой.

Слайд 3


Определение графа Вершины v' и v" называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны одному и тому же ребру. Ребра e' и e" называются смежными, если они имеют, по крайней мере, одну общую вершину (инцидентны одной вершине).
Описание слайда:
Определение графа Вершины v' и v" называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны одному и тому же ребру. Ребра e' и e" называются смежными, если они имеют, по крайней мере, одну общую вершину (инцидентны одной вершине).

Слайд 4


Определение графа Граф, содержащий направленные ребра (дуги) с началом v' и концом v" , называется ориентированным графом (орграфом). Для орграфа Граф, содержащий ненаправленные ребра с конами v' и v" , называется неориентированным графом (нрграфом). Для нрграфа
Описание слайда:
Определение графа Граф, содержащий направленные ребра (дуги) с началом v' и концом v" , называется ориентированным графом (орграфом). Для орграфа Граф, содержащий ненаправленные ребра с конами v' и v" , называется неориентированным графом (нрграфом). Для нрграфа

Слайд 5


Определение графа Рис.1 Неориентированное ребро (a,b) Рис.2 Ориентированное ребро (a,b)
Описание слайда:
Определение графа Рис.1 Неориентированное ребро (a,b) Рис.2 Ориентированное ребро (a,b)

Слайд 6


Определение графа Ребро, концевые вершины которого совпадают, называется петлей. Рис.3. Неориентированная петля Рис.4. Ориентированная петля
Описание слайда:
Определение графа Ребро, концевые вершины которого совпадают, называется петлей. Рис.3. Неориентированная петля Рис.4. Ориентированная петля

Слайд 7


Определение графа Ребра (дуги), имеющие одинаковые начало и конец, называются параллельными или кратными. Рис.5 Кратные неориентированные ребра
Описание слайда:
Определение графа Ребра (дуги), имеющие одинаковые начало и конец, называются параллельными или кратными. Рис.5 Кратные неориентированные ребра

Слайд 8


Определение графа Рис. 6. Кратные ориентированные ребра
Описание слайда:
Определение графа Рис. 6. Кратные ориентированные ребра

Слайд 9


Определение графа Ребра орграфа, соединяющие одну и туже пару вершин в разных направлениях называются симметричными или противоположнонаправленными. Рис. 7. Симметричные ребра
Описание слайда:
Определение графа Ребра орграфа, соединяющие одну и туже пару вершин в разных направлениях называются симметричными или противоположнонаправленными. Рис. 7. Симметричные ребра

Слайд 10


Определение графа Граф называется конечным, если множество его элементов (вершин и ребер) конечно. Рис. 8. Конечный граф
Описание слайда:
Определение графа Граф называется конечным, если множество его элементов (вершин и ребер) конечно. Рис. 8. Конечный граф

Слайд 11


Определение графа Граф называется бесконечным, если бесконечно множество вершин или множество его ребер. Рис. 9. Граф с бесконечным числом вершин
Описание слайда:
Определение графа Граф называется бесконечным, если бесконечно множество вершин или множество его ребер. Рис. 9. Граф с бесконечным числом вершин

Слайд 12


Определение графа Рис. 10. Граф с бесконечным числом ребер
Описание слайда:
Определение графа Рис. 10. Граф с бесконечным числом ребер

Слайд 13


Определение графа Рис. 11. Бесконечный граф
Описание слайда:
Определение графа Рис. 11. Бесконечный граф

Слайд 14


Каноническое соответствие Каждому неориентированному графу канонически соответствует ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющим противоположные направления.
Описание слайда:
Каноническое соответствие Каждому неориентированному графу канонически соответствует ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющим противоположные направления.

Слайд 15


Каноническое соответствие Рис 12. Канонически соответствующие графы
Описание слайда:
Каноническое соответствие Рис 12. Канонически соответствующие графы

Слайд 16


Способы задания Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Пусть вершины графа ; ребра графа G. Граф задают: 1) Матрицей инцидентности 2) Матрицу смежности 3) Списком ребер 3) Рисунком
Описание слайда:
Способы задания Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Пусть вершины графа ; ребра графа G. Граф задают: 1) Матрицей инцидентности 2) Матрицу смежности 3) Списком ребер 3) Рисунком

Слайд 17


Матрица инцидентности матрица инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой для нграфа
Описание слайда:
Матрица инцидентности матрица инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой для нграфа

Слайд 18


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

Слайд 19


Пример: матрица инцидентности н-графа
Описание слайда:
Пример: матрица инцидентности н-графа

Слайд 20


Пример: матрица инцидентности ор-графа
Описание слайда:
Пример: матрица инцидентности ор-графа

Слайд 21


Матрица смежности Матрица смежности размера , столбцам и строкам которой соответствуют вершины графа. Для нграфа равно количеству ребер, связывающих i-ю и j-ю вершины, для орграфа равно количеству ребер выходящих из i-й и входящих в j-ю вершину.
Описание слайда:
Матрица смежности Матрица смежности размера , столбцам и строкам которой соответствуют вершины графа. Для нграфа равно количеству ребер, связывающих i-ю и j-ю вершины, для орграфа равно количеству ребер выходящих из i-й и входящих в j-ю вершину.

Слайд 22


Матрица смежности Матрица смежности нграфа всегда симметрична. Матрица смежности орграфа в общем случае не симметрична. Она симметрична, если данному орграфу есть канонически соответсвующий нграф.
Описание слайда:
Матрица смежности Матрица смежности нграфа всегда симметрична. Матрица смежности орграфа в общем случае не симметрична. Она симметрична, если данному орграфу есть канонически соответсвующий нграф.

Слайд 23


Пример: матрица смежности н-графа
Описание слайда:
Пример: матрица смежности н-графа

Слайд 24


Пример: матрица смежности ор-графа
Описание слайда:
Пример: матрица смежности ор-графа

Слайд 25


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

Слайд 26


Рисунок Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам – линии на плоскости, причем, линия соединяет только те точки, которые соответствуют вершинам, инцидентным данной линии-ребру. Граф для которого возможна геометрическая интерпретация на плоскости, называется планарным.
Описание слайда:
Рисунок Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам – линии на плоскости, причем, линия соединяет только те точки, которые соответствуют вершинам, инцидентным данной линии-ребру. Граф для которого возможна геометрическая интерпретация на плоскости, называется планарным.

Слайд 27


Пример: список ребер н-графа E={(a,a), (a,b), (a,c), (b,c)}
Описание слайда:
Пример: список ребер н-графа E={(a,a), (a,b), (a,c), (b,c)}

Слайд 28


Пример: список ребер ор-графа E={(a,a), (a,b), (a,c), (с,a), (b,c)}
Описание слайда:
Пример: список ребер ор-графа E={(a,a), (a,b), (a,c), (с,a), (b,c)}

Слайд 29


Планарные графы На рисунке приведен пример не планарного графа Рис. 12 Граф «три дома - три колодца»
Описание слайда:
Планарные графы На рисунке приведен пример не планарного графа Рис. 12 Граф «три дома - три колодца»

Слайд 30


Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.
Описание слайда:
Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Слайд 31


Изоморфные графы Рис.13. Изоморфные графы
Описание слайда:
Изоморфные графы Рис.13. Изоморфные графы

Скачать

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