Граф (ЕГЭ-ОГЭ)

• Вершина (узел) — элемент графа, обозначаемый как ${\displaystyle v\in V}$.
• Ребро — связь двух вершин ${\displaystyle v_{1}}$ и ${\displaystyle v_{2}}$, обозначается ${\displaystyle e=\{v_{1},v_{2}\}}$. В ориентированном графе ребро называют дугой и наделяют направлением.
• Порядок графа — количество вершин в графе, обозначаемое как ${\displaystyle n=|V|}$.
• Размер графа — число рёбер в графе, обозначаемое как ${\displaystyle m=|E|}$.
• Степень вершины — количество рёбер, инцидентных вершине ${\displaystyle v}$, обозначаемое ${\displaystyle d(v)}$.

Простой граф не содержит петель (рёбер, соединяющих вершину саму с собой) и кратных рёбер. Рёбра задаются неупорядоченными парами различных вершин: ${\displaystyle G=\langle V,E\rangle ,\quad E\subseteq \{\{v_{i},v_{j}\}\mid v_{i},v_{j}\in V,\ v_{i}\neq v_{j}\}}$.

В ориентированном графе рёбра, называемые дугами, имеют направление и задаются упорядоченными парами вершин: ${\displaystyle G=\langle V,E\rangle ,\quad E\subseteq \{(v_{i},v_{j})\mid v_{i},v_{j}\in V\}}$.

В взвешенном графе каждому ребру сопоставлен числовой вес: ${\displaystyle w:E\rightarrow \mathbb {R} }$.

Двудольный граф — это граф, вершины которого разделены на два непересекающихся множества ${\displaystyle V_{1}}$ и ${\displaystyle V_{2}}$, а каждое ребро связывает вершины из разных подмножеств.

Планарный граф — такой граф, который можно вывести на плоскости так, что пересечения рёбер происходят лишь в вершинах.

Матрица смежности — это квадратная матрица ${\displaystyle A}$ размера ${\displaystyle n\times n}$, в которой элемент ${\displaystyle a_{ij}}$ равен 1, если между вершинами ${\displaystyle v_{i}}$ и ${\displaystyle v_{j}}$ существует ребро, и 0 в противном случае.

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

• Маршрут — упорядоченная последовательность вершин, в которой каждая пара соседних вершин связана ребром.
• Цепь — маршрут, не содержащий повторяющихся рёбер.
• Простая цепь — маршрут, в котором вершины не повторяются.
• Цикл — цепь, чья начальная и конечная вершины совпадают.

• Связный граф — граф, где между любыми двумя вершинами имеется путь.
• Компонента связности — максимальный по включению связный подграф.
• Дерево — связный граф без циклов.
• Лист — вершина, имеющая степень 1.
• Мост — ребро, при удалении которого число компонент связности увеличивается.

• Обход в глубину (DFS) — алгоритм поиска и обхода вершин графа, осуществляющий углубление в каждую ветвь.
• Обход в ширину (BFS) — алгоритм, который просматривает граф по уровням, начиная с исходной вершины и последовательно посещая всех её соседей.
• Алгоритм Дейкстры — метод поиска кратчайших путей от одной заданной вершины до всех остальных в графе с неотрицательными весами рёбер.

Графы используются для моделирования:

• Социальных сетей (вершины представляют людей, рёбра — их связи).
• Транспортных сетей (города в роли вершин и дороги в качестве рёбер).
• Электрических схем.
• Структур данных и связей в программировании.
• Интернет-сетей (узлы и соединения между ними).

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