Граф, вершина, ребро (дуга), петля, изолированная точка, висячая (концевая точка), степень вершины. Теорема о сумме степеней вершин. Ориентированный и неориентированный граф.

Основные понятия теории графов

Основные определения:

• Граф – это множество вершин и ребер, соединяющих пары вершин.
• Вершина (узел) – элемент графа, обозначаемый точкой.
• Ребро (дуга) – линия, соединяющая две вершины. В ориентированном графе ребро имеет направление.
• Петля – ребро, соединяющее вершину саму с собой.
• Изолированная точка – вершина, не имеющая ни одного ребра.
• Висячая (концевая) точка – вершина, соединенная ровно с одним ребром.
• Степень вершины – количество ребер, инцидентных данной вершине.

Теорема о сумме степеней вершин:

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

Типы графов:

• Ориентированный граф: Ребра имеют направление (направленные дуги).
• Неориентированный граф: Ребра не имеют направления.