Связность

Граф называется связным, если любые две его различные вершины соединяет цепь. На множестве вершин графа определим отношение , если или если в графе существует цепь, соединяющая a и b. Отношение является отношением эквивалентности. Пусть – классы эквивалентности множества вершин графа , определяемые этим отношением. Подграфы ,…, графа G называются компонентами связности этого графа, а их число называется степенью связности графа. Если граф имеет несколько компонентов связности, то вершины можно перенумеровать так, что его матрица инцидентности клеточно диагональна.

ТЕОРЕМА. Ранг матрицы инцидентности графа, имеющего компонент связности и n вершин, равен n – .

Доказательство. Достаточно доказать, что ранг матрицы М связного графа c n вершинами равен n – 1. Так как в каждой строке матрицы по две единицы, то сумма всех столбцов по модулю 2 нулевая < n. Если один столбец матрицы удалить, то в некоторых строках останется по одной единице. Если предположить, что r (M) < n – 1, то в столбцах должно быть чётное число единиц, а это противоречит только что сказанному. ■

В связном графе ребро называется перешейком, если после его удаления из графа свойство его связности исчезает. Связный граф без циклов называется деревом.