1.1.5 Описание графа с помощью матрицы циклов

        Для графа G, имеющего n вершин и m ребер, матрица циклов имеет размерность к x m, где к – число циклов в графе. Элемент этой матрицы сij=1, если j-ое ребро входит в i-ый цикл и сij=0 в противном случае.

Для графа на рис.1.2 матрица циклов имеет вид:

1.1.6 Описание графа с помощью матрицы разрезов

        Если задан связный граф G=(V, E) и множество его вершин разбито на два непустых подмножества W и W/, то множество ребер, соединяющих W с W/ называют разрезом. Простым называют разрез, разбивающий связный граф только на две компоненты связности. С использованием простых разрезов можно построить матрицу разрезов графа. Для графа G, имеющего n вершин и m ребер, матрица разрезов имеет размерность l x m, где l – число разрезов на графе. Элемент этой матрицы кij=1, если j-ое ребро входит в i-ый разрез и кij=0 в противном случае.