Как найти матрицу инцидентности графа: пошаговое решение

Дано: неориентированный граф на пяти вершинах $v_1, v_2, v_3, v_4, v_5$ с шестью рёбрами $e_1 = v_1v_2$, $e_2 = v_1v_3$, $e_3 = v_2v_3$, $e_4 = v_2v_4$, $e_5 = v_3v_5$, $e_6 = v_4v_5$. Найти: матрицу инцидентности этого графа, а затем её вариант со знаками для орграфа.

Матрица инцидентности строится механически: строк столько, сколько вершин, столбцов столько, сколько рёбер, а единица в клетке означает, что вершина является концом этого ребра. Размер матрицы здесь $5 \times 6$, в каждом столбце ровно две единицы, всего их двенадцать. Ответ: строки матрицы равны 1 1 0 0 0 0; 1 0 1 1 0 0; 0 1 1 0 1 0; 0 0 0 1 0 1; 0 0 0 0 1 1, а их суммы 2, 3, 3, 2, 2 совпадают со степенями вершин. Калькулятор сверху открыт ровно на этом графе: сними ребро, и столбец исчезнет вместе с отрезком на схеме.

Решение по шагам

Дано. Граф $G = (V, E)$ без петель и кратных рёбер, где

$$V = \{v_1, v_2, v_3, v_4, v_5\}, \qquad E = \{v_1v_2,\ v_1v_3,\ v_2v_3,\ v_2v_4,\ v_3v_5,\ v_4v_5\}.$$

Найти. Матрицу инцидентности $\mathbf{B}$ размера $5 \times 6$ и матрицу инцидентности орграфа, полученного ориентацией каждого ребра от вершины с меньшим номером к вершине с большим.

Шаг 1. Фиксируем порядок вершин и рёбер. Это не формальность: матрица зависит от нумерации, и если рёбра заданы списком, порядок списка становится порядком столбцов. Вершины идут сверху вниз как $v_1, \dots, v_5$, рёбра слева направо в порядке условия: $e_1 = v_1v_2$, $e_2 = v_1v_3$, $e_3 = v_2v_3$, $e_4 = v_2v_4$, $e_5 = v_3v_5$, $e_6 = v_4v_5$. Дальше остаётся заполнить пустую таблицу пять на шесть.

Шаг 2. Заполняем столбцы по одному ребру. Удобнее идти не по строкам, а по столбцам: каждое ребро даёт ровно две единицы, и обе ставятся сразу. Берём $e_1 = v_1v_2$ - единицы в строках $v_1$ и $v_2$, остальные три клетки столбца нулевые. Берём $e_2 = v_1v_3$ - единицы в строках $v_1$ и $v_3$. И так до последнего ребра.

Шаг 3. Записываем ответ матрицей. Тот же результат в привычной записи, где строка номер $i$ отвечает вершине $v_i$, а столбец номер $j$ - ребру $e_j$:

$$\mathbf{B} = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}.$$

Шаг 4. Проверяем себя двумя суммами. Сумма каждого столбца обязана равняться двум: у ребра два конца, третьего не дано. Сумма строки $i$ равна степени вершины $v_i$, потому что строка перечисляет все инцидентные ей рёбра. Получаем $\deg v_1 = 2$, $\deg v_2 = 3$, $\deg v_3 = 3$, $\deg v_4 = 2$, $\deg v_5 = 2$. Общее число единиц равно $2 \cdot 6 = 12$, и это же число получается как сумма степеней - знакомая лемма о рукопожатиях, которую подробно разбирает страница о том, как найти степени вершин графа.

Шаг 5. Ориентируем рёбра и расставляем знаки. Пусть каждая дуга идёт от вершины с меньшим номером к вершине с большим: $v_1 \to v_2$, $v_1 \to v_3$, $v_2 \to v_3$, $v_2 \to v_4$, $v_3 \to v_5$, $v_4 \to v_5$. В столбце дуги теперь стоит $+1$ у начала и $-1$ у конца:

$$\mathbf{B}_{\text{ор}} = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & 1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & -1 \end{pmatrix}.$$

Проверка здесь другая: сумма каждого столбца равна нулю, потому что $+1$ и $-1$ гасят друг друга. Суммы строк дают $2, 1, -1, 0, -2$ - это разности полустепеней исхода и захода, и в сумме по всем вершинам они обязаны давать ноль.

Ответ. Матрица инцидентности имеет размер $5 \times 6$, её строки равны $(1,1,0,0,0,0)$, $(1,0,1,1,0,0)$, $(0,1,1,0,1,0)$, $(0,0,0,1,0,1)$, $(0,0,0,0,1,1)$; суммы строк $2, 3, 3, 2, 2$ совпадают со степенями вершин, суммы столбцов равны 2. Для орграфа та же матрица получает минусы у концов дуг, и суммы её столбцов равны нулю.

Что стоит в клетке матрицы инцидентности

Определение занимает одну строку, и всё остальное из него выводится. Для неориентированного графа с вершинами $v_1, \dots, v_n$ и рёбрами $e_1, \dots, e_m$ матрица инцидентности $\mathbf{B} = (b_{ij})$ имеет размер $n \times m$, причём

$$b_{ij} = \begin{cases} 1, & \text{если вершина } v_i \text{ инцидентна ребру } e_j, \\ 0, & \text{иначе}. \end{cases}$$

Слово «инцидентна» означает ровно «является концом»: вершина и ребро инцидентны, вершина и вершина смежны. Отсюда и главное отличие от матрицы смежности - та квадратная и описывает пары вершин, а эта прямоугольная и описывает пары «вершина и ребро».

Петля выбивается из схемы, и на ней чаще всего спотыкаются. У петли оба конца в одной вершине, поэтому в её столбце стоит либо двойка, либо, в другой распространённой договорённости, единица; какое соглашение принято в вашем курсе, стоит подписать рядом с матрицей. Кратные рёбра, в отличие от петель, проблемы не создают: каждое получает свой столбец, и в матрице появляются два одинаковых столбца - то самое, чего матрица смежности показать не умеет.

Матрица инцидентности орграфа: откуда берутся знаки

В ориентированном графе у дуги есть начало и конец, и одной единицы уже мало: иначе дуга $v_1 \to v_2$ и дуга $v_2 \to v_1$ дали бы одинаковые столбцы. Поэтому в клетке ставят

$$b_{ij} = \begin{cases} +1, & v_i \text{ - начало дуги } e_j, \\ -1, & v_i \text{ - конец дуги } e_j, \\ 0, & \text{вершина не инцидентна дуге}. \end{cases}$$

Встречается и обратное соглашение, где минус ставят у начала, а плюс у конца. По существу оно ничего не меняет: вся матрица умножается на $-1$. Важно лишь не смешивать два соглашения внутри одной задачи.

Суммы строк в ориентированном случае читаются по-другому. Строка вершины $v_i$ содержит столько плюс единиц, сколько дуг из неё выходит, и столько минус единиц, сколько в неё входит, поэтому сумма строки равна $\deg^{+} v_i - \deg^{-} v_i$. У нас $v_1$ даёт $2 - 0 = 2$, $v_4$ даёт $1 - 1 = 0$, $v_5$ даёт $0 - 2 = -2$, а сумма всех этих чисел равна нулю: каждая дуга учтена один раз со знаком плюс и один раз со знаком минус.

Связь с матрицей смежности и степенями вершин

Матрица инцидентности и матрица смежности связаны одним произведением, и это самая полезная формула темы. Если $\mathbf{A}$ - матрица смежности простого графа, а $\mathbf{D}$ - диагональная матрица степеней вершин, то для неориентированной матрицы инцидентности выполняется

$$\mathbf{B}\mathbf{B}^{\mathsf{T}} = \mathbf{A} + \mathbf{D}.$$

Проверим на нашем примере хотя бы одну клетку. Строка $v_1$ равна $(1,1,0,0,0,0)$, строка $v_2$ равна $(1,0,1,1,0,0)$; их скалярное произведение равно единице - столько общих рёбер у вершин $v_1$ и $v_2$, и ровно это стоит в матрице смежности. На главной диагонали получается скалярный квадрат строки, то есть число единиц в ней, то есть степень вершины.

Для ориентированной матрицы знаки переворачивают результат, и произведение даёт матрицу Кирхгофа (лапласиан):

$$\mathbf{B}_{\text{ор}}\mathbf{B}_{\text{ор}}^{\mathsf{T}} = \mathbf{D} - \mathbf{A}.$$

На диагонали окажутся степени $2, 3, 3, 2, 2$, а вне диагонали минус единицы на местах рёбер. Из-за этой формулы ориентированную матрицу любят в спектральной теории графов: лапласиан собирается из неё одним умножением.

Ранг матрицы инцидентности и что он показывает

Ранг ориентированной матрицы инцидентности равен $n - k$, где $k$ - число компонент связности; для связного графа это $n - 1$. Наш граф связен, значит ранг равен $5 - 1 = 4$, что и показывает калькулятор. Причина проста: сумма всех строк равна нулевой строке, поэтому строки линейно зависимы и ранг не достигает пяти.

Польза от этого факта двойная. Во-первых, ранг даёт число компонент связности без обхода графа: посчитали ранг, например приведением матрицы к ступенчатому виду, и число компонент равно $n$ минус ранг. Во-вторых, линейно независимые наборы столбцов - это в точности наборы рёбер без циклов; максимальный такой набор из $n - 1$ столбца задаёт остовное дерево, и на этом свойстве держатся жадные алгоритмы вроде алгоритма Прима.

С неориентированной матрицей осторожнее: над обычными числами её ранг равен $n$, если в компоненте есть цикл нечётной длины, и $n - 1$ для двудольной компоненты. В нашем графе есть треугольник $v_1v_2v_3$, поэтому ранг матрицы $\mathbf{B}$ равен пяти, а не четырём. Если в задаче про ранг не сказано, какая матрица имеется в виду, почти всегда подразумевается ориентированная.

Частые ошибки

• Путают инцидентность и смежность. Матрица смежности квадратная, размера $n \times n$, и описывает пары вершин; матрица инцидентности прямоугольная, размера $n \times m$. Если у вас получилась квадратная таблица не случайно, а «по определению», вы построили не ту матрицу.
• Ставят строки-рёбра, а столбцы-вершины. Стандарт: строки - вершины, столбцы - рёбра. Транспонированный вариант встречается, но о нём надо предупредить явно.
• Теряют вторую единицу в столбце. Столбец заполняется целиком за один раз: отметили оба конца ребра и только потом переходите к следующему. Сумма каждого столбца ровно два - проверка занимает пять секунд.
• В орграфе забывают знак. Матрица из одних единиц не отличает дугу $v_1 \to v_2$ от дуги $v_2 \to v_1$. Признак ошибки: сумма столбца равна двум вместо нуля.
• Неверно обходятся с петлёй. Петля инцидентна одной вершине дважды, и в её столбце стоит 2 (или 1 при другом соглашении), но никак не две единицы в разных строках.
• Меняют нумерацию посередине решения. Перестановка вершин переставляет строки, перестановка рёбер - столбцы. Матрица от этого остаётся верной, но не совпадёт с эталоном, поэтому порядок фиксируют один раз в начале.

FAQ

Чем матрица инцидентности лучше матрицы смежности? Она показывает кратные рёбра и кодирует рёбра как самостоятельные объекты, что удобно для потоковых задач и линейной алгебры на графах. Зато проверка смежности двух вершин по ней медленнее, а для плотных графов она занимает больше памяти.

Как восстановить граф по матрице инцидентности? Идти по столбцам: в каждом ровно две единицы (или пара $+1$ и $-1$), и номера их строк дают концы ребра. Из матрицы со строками 1 1 0 0; 1 0 1 0; 0 1 1 1; 0 0 0 1 получаются рёбра $v_1v_2$, $v_1v_3$, $v_2v_3$, $v_3v_4$, то есть треугольник с подвешенной вершиной.

Можно ли по матрице инцидентности найти расстояния между вершинами? Напрямую нет: в ней хранится только отношение «вершина принадлежит ребру». Расстояния, радиус и диаметр графа считают обходом в ширину или по степеням матрицы смежности, а матрица инцидентности при этом служит лишь исходным описанием графа.

Сколько единиц в матрице инцидентности графа с m рёбрами? Ровно $2m$ ненулевых клеток, независимо от числа вершин: каждое ребро отмечается у обоих концов. Остальные $nm - 2m$ клеток нулевые, поэтому в программах такую матрицу обычно хранят списком рёбер.

Коротко

1. Строки матрицы инцидентности - вершины, столбцы - рёбра; размер $n \times m$, в клетке единица, если вершина является концом ребра.
2. Заполняйте по столбцам: каждое ребро сразу даёт две единицы, сумма любого столбца равна двум, всего единиц $2m$.
3. Сумма строки равна степени вершины, поэтому строки матрицы - готовая проверка по лемме о рукопожатиях.
4. В орграфе ставят $+1$ у начала дуги и $-1$ у конца; суммы столбцов становятся нулевыми, а суммы строк дают разность полустепеней.
5. Для примера из условия матрица имеет размер $5 \times 6$ со строками 1 1 0 0 0 0; 1 0 1 1 0 0; 0 1 1 0 1 0; 0 0 0 1 0 1; 0 0 0 0 1 1, степени вершин равны 2, 3, 3, 2, 2, а ранг ориентированной матрицы равен 4.