Теорема. Алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой

Алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

Пример 5. Матрица Кирхгофа для графа на рис. 5

Определение. Простой граф, в котором любые две вершины смежны, называется полным графом и обозначается , где – число вершин.

Примеры полных графов:

Рис. 8 Рис. 9

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

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

Рис. 10 Рис. 11 Рис. 12 Рис. 13

Если каждая вершина из соединена ребром с каждой вершиной из , то такой граф называется полным двудольным графом, обозначается , где и – мощности подмножеств и . На рис. 11 и рис. 12 изображены графы и . Среди полных двудольных графов выделяется граф , который называется звездным графом, на рис. 13 изображен граф .

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