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

Определение графа

Пусть V – множество вершин,
а Е – множество ребер.
Графом

Определение графа

Вершины v' и v" называются смежными, если существует ребро, соединяющее

Определение графа

Граф, содержащий направленные ребра (дуги) с началом v' и концом

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

Определение графа

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

Определение графа

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

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

Определение графа

Ребра орграфа, соединяющие одну и туже пару вершин в разных

Определение графа

Граф называется конечным, если множество его элементов (вершин и ребер)

Определение графа

Граф называется бесконечным, если бесконечно множество вершин или множество его

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

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

Каноническое соответствие

Каждому неориентированному графу канонически соответствует ориентированный граф с тем же

Каноническое соответствие
Рис 12. Канонически соответствующие графы

Способы задания

Задать граф – значит описать множества его вершин и ребер,

Матрица инцидентности

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

Матрица инцидентности

для орграфа

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

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

Матрица смежности

Матрица смежности
размера , столбцам и строкам которой соответствуют вершины

Матрица смежности

Матрица смежности нграфа всегда симметрична.
Матрица смежности орграфа в общем случае

Пример: матрица смежности н-графа

Пример: матрица смежности ор-графа

Список ребер

Списком ребер можно задать граф без кратных ребер.
Ребро представляется парой

Рисунок

Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам

Пример: список ребер н-графа

E={(a,a), (a,b), (a,c), (b,c)}

Пример: список ребер ор-графа

E={(a,a), (a,b), (a,c), (с,a), (b,c)}

Планарные графы

На рисунке приведен пример не планарного графа
Рис. 12 Граф

Изоморфные графы

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