3.4.1.4. Введение и удаление ребер графа

Если удалить ребро (x_i, x_j) графа G=<X, r>, где x_i, x_jX, то не следует удалять инцидентные данному ребру вершины. В результате будет получен новый граф G’=<X’, r’>, где X’=X, r’=r\(x_i, x).

Если добавить ребро (x_i, x_j) в граф G=<X, r>, где x_i, x_jX, то удобно использовать матрицу инциденции, каждая строка которой для контроля содержит ровно две “1”. В результате получен новый граф G’=<X’, r’>, где X'=X, r’=r\(x_i, x).

3.4.1.5. Поиск плотности и неплотности графа

Для определения плотности графа достаточно вычислить матрицу достижимости ||q|| = Ir и выполнить перестановки строк и столбцов так, чтобы найти блоки матрицы, описывающие клику графа.

Пусть дана матрица смежности ||r||,

r	x1	x2	x3	x4	x5	x6	x7	x8
x1	0	1	1	0	1	0	1	1
x2	1	0	1	0	0	0	0	0
x3	1	1	0	1	1	0	1	0
x4	0	0	1	0	1	0	0	0
x5	1	0	1	1	0	1	1	0
x6	0	0	0	0	1	0	1	0
x7	1	0	1	0	1	1	0	1
x8	1	0	0	0	0	0	1	0

q	x1	x2	x3	x4	x5	x6	x7	x8	Матрица достижимости ||q||= I||r|| формируется добавление ”1” на главной диагонали матрицы ||r||. В матрице достижимости есть три блока {x1, x2, x3}, {x3, x4, x5}, {x5, x6, x7}, отражающих три полных подграфа.
x1	1	1	1	0	1	0	1	1
x2	1	1	1	0	0	0	0	0
x3	1	1	1	1	1	0	1	0
x4	0	0	1	1	1	0	0	0
x5	1	0	1	1	1	1	1	0
x6	0	0	0	0	1	1	1	0
x7	1	0	1	0	1	1	1	1
x8	1	0	0	0	0	0	1	1

Однако, если выполнить перестановки строк и столбцов матрицы (это может быть повторено n! раз), то будет найден блок, опирающийся на четыре вершины. Например, {x₁, x₃, x₅, x₇}.

	x1	x3	x5	x7	x2	x4	x6	x8
x1	1	1	1	1	1	0	0	1
x3	1	1	1	1	1	1	0	0
x5	1	1	1	1	0	1	1	0
x7	1	1	1	1	1	0	1	1
x2	1	1	0	0	1	0	0	0
x4	0	1	1	0	0	1	0	0
x6	0	0	1	1	0	0	1	0
x8	1	0	0	1	0	0	0	1

Следовательно,(G)=4. См. граф на рис. 3.14.

Для определения неплотности графа необходимо найти дополнительный граф G=<X, r>, определить для него матрицу достижимости ||q^-||=I||r|| и выполнить необходимое число перестановок строк и столбцов, чтобы найти блоки, опирающиеся на наибольшее число вершин. Для графа, приведенного на рис. 3.14 найдем матрицу ||r|| дополнительного графа и матрицу достижимости ||q^-||=I||r||. Для данного графа ||r|| = ||q||.

r	x1	x2	x3	x4	x5	x6	x7	x8
x1	1	0	0	1	0	1	0	0
x2	0	1	0	1	1	1	1	1
x3	0	0	1	0	0	1	0	1
x4	1	1	0	1	0	1	1	1
x5	0	1	0	0	1	0	0	1
x6	1	1	1	1	0	1	0	1
x7	0	1	0	1	0	0	1	0
x8	0	1	1	1	1	1	0	1

В результате перестановок строк и столбцов получено два блока: {x₂, x₄, x₆, x₈}, (x₇, x₂, x₄}. Число вершин в одном из них равно четырем. Следовательно,(G)=(G)=4.

q^-	x1	x3	x5	x7	x2	x4	x6	x8
x1	1	0	0	0	0	1	1	0
x3	0	1	0	0	0	0	1	1
x5	0	0	1	0	1	0	0	1
x7	0	0	0	1	1	1	0	0
x2	0	0	1	1	1	1	1	1
x4	1	0	0	1	1	1	1	1
x6	1	1	0	0	1	1	1	1
x8	0	1	1	0	1	1	1	1