Графы. Вершины и рёбра графа. Степень вершины.

### Понимание графов, вершин и рёбер Граф — это математическая структура, состоящая из множества объектов, называемых *вершинами*, и множества связей между ними, называемых *рёбрами*. #### 1. Вершины и рёбра графа - **Вершины** (или узлы) — это элементы графа. Каждая вершина может представлять что угодно: людей в социальном графе, города на карте и так далее. - **Рёбра** — это связи между парами вершин. Ребро может быть направленным (указывающим от одной вершины к другой) или ненаправленным (без указания направления). Для иллюстрации представьте, что у вас есть три города (вершины): A, B и C. Связи (рёбра) между ними могут выглядеть следующим образом: - A — B (ребро между городами A и B) - B — C (ребро между городами B и C) - A — C (если между A и C тоже есть связь) #### 2. Степень вершины *Степень вершины* — это количество рёбер, инцидентных данной вершине. В зависимости от того, направленный у нас граф или ненаправленный, степень может считаться по-разному: - **Для ненаправленного графа:** степень вершины равна количеству рёбер, соединяющих эту вершину с другими вершинами. Например, если у вершины A имеется рёбра с B и C, то степень вершины A равна 2. - **Для направленного графа:** у нас есть две степени: - **Входная степень** (или инцидентная степень) — количество рёбер, указывающих на вершину. - **Исходящая степень** — количество рёбер, указывающих от вершины. **Пример:** Рассмотрим направленный граф с вершинами A, B и C: - Из A в B — 1 ребро (исходящее из A). - Из A в C — 1 ребро (исходящее из A). - Из B в C — 1 ребро (исходящее из B). Теперь для степени вершин: - Степень A: Исходящая 2 (к B и C), Входная 0 (нет рёбер, указывающих на A). - Степень B: Исходящая 1 (к C), Входная 1 (от A). - Степень C: Исходящая 0, Входная 2 (от A и B). ### Заключение Графы являются важной частью комбинаторики и информатики, и понимание вершин, рёбер и степени вершин помогает решать многие задачи, связанные с моделированием и анализом. Если у вас есть дополнительные вопросы или интересуют примеры задач, не стесняйтесь спрашивать!