Расскажи о неориентированном графе и его свойствах.

Неориентированный граф — это пара $(V, E)$, где $V$ — множество вершин (узлов), а $E$ — множество рёбер. Каждое ребро представляет собой неупорядоченную пару ${u, v}$ вершин $u, v \in V$.

Основные свойства:

• Ребра без направления: Связь между вершинами симметрична. Если есть ребро между $u$ и $v$, это означает, что можно перемещаться как из $u$ в $v$, так и из $v$ в $u$.
• Степень вершины: Количество рёбер, инцидентных данной вершине. Обозначается как $deg(v)$.
• Сумма степеней вершин: В любом неориентированном графе сумма степеней всех вершин равна удвоенному количеству рёбер. $\sum_{v \in V} deg(v) = 2|E|$.
• Путь: Последовательность вершин $v_0, v_1, ..., v_k$, где каждая пара $(v_i, v_{i+1})$ является ребром.
• Цикл: Путь, который начинается и заканчивается в одной и той же вершине, при этом все остальные вершины уникальны.
• Связность: Граф называется связным, если существует путь между любой парой вершин. Несвязный граф состоит из нескольких связных компонент.
• Взвешенный граф: Каждому ребру может быть присвоено некоторое числовое значение (вес).
• Отсутствие петель и кратных рёбер (простой граф): В простых неориентированных графах между двумя вершинами может быть не более одного ребра, и рёбра не соединяют вершину саму с собой (нет петель).
• Полный граф: Граф, в котором каждая пара различных вершин соединена ребром. Обозначается $K_n$, где $n$ — количество вершин.
• Двудольный граф: Множество вершин можно разбить на два непересекающихся подмножества $U$ и $W$, такие что каждое ребро соединяет вершину из $U$ с вершиной из $W$.