Тапсырма № 4 · ОГЭ

Смежность вершин

Как определить, соединены ли две вершины графа одним ребром

2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

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

Смежные вершиныСлово «смежный» означает «находящийся рядом, имеющий общую границу».

Смежные вершины — это две различные вершины графа, инцидентные одному и тому же ребру. Иначе говоря, между ними есть прямое соединение. Смежность относится к паре вершин: если вершина A смежна с вершиной B, то и B смежна с A.

Чтобы проверить смежность на рисунке, выберите две вершины и проследите, есть ли между ними одно ребро. Если линия идёт сначала к промежуточной вершине, то выбранные вершины не смежны: они могут быть связаны маршрутом, но не напрямую. При поиске удобно мысленно перечислять все концы каждого ребра.

\[A_{ij}=\begin{cases}1, & \text{если вершины } i \text{ и } j \text{ смежны},\\0, & \text{иначе.}\end{cases}\]1

В этой жазбалар \(A_{ij}\) — элемент матрицы смежности. Для неориентированного графа выполняется \(A_{ij}=A_{ji}\): смежность взаимна. Петли и кратные рёбра в школьных задачах обычно не рассматриваются; если петля разрешена, её конец относится к той же вершине.

№

Пример

Пусть рёбра графа: AB, AC, BD и CD. Вершины A и B смежны, потому что соединены ребром AB. Вершины A и D не смежны: путь A–B–D существует, но прямого ребра AD нет. Вершины B и C также не смежны.

Не путайте со степенью вершины

Степень вершины — это количество рёбер, соединённых с данной вершиной. Смежность отвечает на другой вопрос: соединены ли напрямую две выбранные вершины. Наличие общего соседа ещё не делает вершины смежными.

Быстрая проверка

У графа есть рёбра AB, BC и CD. Какие пары вершин смежны?

Главное за минуту

Главное

Смежные вершины соединены одним общим ребром.
Для проверки ищите прямую связь между выбранными вершинами, а не любой путь между ними.
Смежность двух вершин не равна степени вершины: степень показывает число её соседей.