Графы. Основные определения, способы задания - презентация, доклад, проект скачать

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

Графы. Основные определения, способы задания, слайд №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 инцидентны друг другу, если вершина является для этого ребра концевой точкой.

Слайд 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

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

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