Графы: основные понятия
dlyachainikov.ru · Дискретная математикаОсновные понятия графа
- Граф обозначается как G = (V, E), где V — множество вершин, а E — множество рёбер.
Виды графов
- Неориентированный граф: рёбра не имеют направления.
- Ориентированный граф (орграф): каждое ребро имеет направление.
- Пустой граф: граф с вершинами, но без рёбер.
- Полный граф: каждая пара вершин соединена рёбром.
Элементы графа
- Вершина (узел): элемент множества V.
- Ребро: упорядоченная или неупорядоченная пара вершин.
Свойства степени
- Сумма степеней всех вершин равна удвоенному числу рёбер: .