Контрольная работа: Графы

Матрицей смежности графа, содержащего n-вершин, называется квадратная матрица А_nxn , каждый элемент которой а_ij определяется следующим образом:

1, если вершины i и j соединены ребром или дугой;

a_ij =

0, в противном случае.

Для графа с кратными ребрами (дугами) вместо 1 записывается число ребер (дуг) между вершинами i и j.

Для неориентированного графа, матрица смежности имеет размерность (7 х 7) и записывается в виде

1 2 3 4 5 6 7

А=

Слева и сверху проставлены номера вершин.

Для ориентированного графа, матрица смежности имеет размерность (4 х 4) и записывается в виде

1 2 3 4

А=

Матрицу смежности чаще применяют для задания неориентированного графа. Для задания ориентированного графа лучше использовать матрицу инцидентности.

Матрицей инцидентности ориентированного графа с n вершинами и m ребрами называется матрица В с n строками и m столбцами, элемент которой b_ij определяется следующим образом:

1, если вершина является началом ребра (i, j);

-1,если вершина является концом ребра (i, j);

b_ij = 2, если вершина и начало, и конец ребра (i, j);

0, если вершина и ребро не инцидентны.

Для ориентированного графа, матрица инцидентности В_4х5 имеет следующий вид:

1 2 3 4 5

В=

Взвешенный ориентированный граф без петель, в котором выделено k -вершин, называемых полюсами, является k -полюсной цепью. Среди сетей особо выделяется двухполюсная транспортная сеть (рис. 14) S=(N, U) с множеством вершин N и множеством дуг U , для которых выполняется следующее условие:

1) существует только одна вершина сети s є N , в которую не заходит ни одна дуга. Эта вершина называется входом, или истоком сети;

2) существует только одна вершина сети t є N , из которой не выходит ни одной дуги сети. Эта вершина называется выходом, или стоком сети;

3) каждой дуге сети u є U поставлено в соответствие неотрицательное число с (u ), называемое пропускной способностью дуги.

Рис. 14

Примерами вершин сети могут быть пересечения автострад, электростанции, телефонные узлы, железнодорожные узлы, аэропорты, водохранилища, товарные склады.

Примерами дуг сети могут быть дороги, линии электропередачи, телефонные линии, авиалинии, водные магистрали, нефте- и газопроводы.