Упражнения

1.1. Дан граф G

a) определить – к какому типу относится граф;

), v

в) указать кратности ребер (v₁, v₂), (v₃, v₅);

д) указать имеющиеся циклы, простые циклы;

е) указать ребра, смежные ребру (v₁, v₂);

ж) какие вершины инцидентны ребру (v₆, v₅)?

1.2. Составить матрицы смежности и инцидентности графов:

в)

Какими свойствами обладают данные матрицы?

1.3. Орграф задан матрицей инцидентности. Не строя графа, определить какие имеются контуры в графе. Какова полустепень исхода вершин v₁, v₄ и полустепень захода вершины v₃.

1.4. Орграф задан матрицей смежности. Выяснить, имеются ли контуры в графе.

а) б) в)

1.5. Орграф D c множеством вершин V{1, 2, 3, 4, 5, 6, 7} задан списком ребер X = {(1, 4), (1, 6), (2, 1), (2, 2), (2, 6), (2, 6), (3, 2), (3, 4), (4, 6), (5, 2), (5, 4), (5, 4), (5, 5), (6.2), (6, 5), (7, 1), (7, 6)}.

Построить реализацию графа D.

1.6. Зная матрицу смежности ориентированного псевдографа, определить количество путей длины 1, 2, 3 из v₃ в v₂, из v₂ в v₄.Имеет ли контур данный орграф?

А(D) =

1.7. С помощью матрицы A(D) определить, сколько путей длины 2, 3, 4 существует из вершины v₁ в вершину v₂:

А(D) =

Построить граф и найти эти пути.

1.8. Даны графы G₁ и G₂. Построить графы G₁UG₂, G₁×G₂.

Определение: (m x n) – матрицу C= [с_ij], у которой с_ij {0;1}, где i = 1,2,…,m; j = 1,2,…,n будем называть булевойматрицей.

Замечание. В случае, если G граф без кратных ребер, то матрица смежности A(G) состоит из нулей и единиц, т.е. является булевой.

Над булевыми матрицами одинаковой размерности будем производить обычные логические операции.

1) Дизъюнкция (конъюкция)

Если C=[с_ij] и Д=[d_ij] – матрицы размерности m x n, то F=[f_ij]=C Д (С Д), есть матрица размерности m x n, у которой каждый элемент f_ij определяется следующим образом: f_ij= с_ij d_ij (с_ij d_ij) (i=1,2…,m; j=1,2…,n).

2) Логическоеумножение

Пусть C= [с_ij] – булева матрица размерности m x k, Д=[d_ij] – булева матрица размерности kxn. Тогда F= [f_ij]=C*Д – булева матрица размерности m x n, у которой каждый элемент f_ij определяется следующим образом:

f_ij=

Если К=С₁* С₂*…* С_k , причем С₁= С₂=…= С_k= С где С – квадратичная булева матрица, то будем писать .

Введем теперь операцию sign перехода от произвольной m x n матрицы Д=[d_ij] c неотрицательными элементами к булевой m x n матрице С= [c_ij]=signД, у которой c_ij=sign d_ij (i=1,2,…,m; j=1,2…,n), где для любого числа t 0: .

Свойства операции sign:

Sign(Д₁+Д₂) = sign Д₁ sign Д₂

Sign(Д₁×Д₂) = sign Д₁ * sign Д₂

Замечание. Булевы матрицы более экономичны в вычислительном отношении, чем целочисленные. Запоминание булевой матрицы требует меньшего объема оперативной памяти ЭВМ, чем запоминание целочисленной матрицы той же размерности. Кроме того, выполнение на ЭВМ логических операций над булевыми матрицами требует меньшего объема вычислений, чем над целочисленными.

Вернемся к задаче о вычислении наличия контуров в орграфе.

Утверждение: Для того, чтобы n-вершинный орграф Д c матрицей смежности А=А(Д) имел хотя бы один контур, необходимо и достаточно, чтобы матрица имела ненулевые диагональные элементы.