Слайд 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. Изоморфные графы
