Графы. Матричное задание графов. Матрица смежности, матрица инцидентности. Привести примеры.

Граф может быть представлен как в виде рисунка, так и в виде матрицы. Это бывает необходимо при большом числе вершин и дуг (ребер), когда рисунок теряет свою наглядность. Матричное представление графов используется при исследовании его на ЭВМ.

Пусть D = (V, Х) – орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой

Определение. Матрицей инцидентности орграфа D называется (nґm) –матрица B(D)=[bij], у которой

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v1,v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Определение. Матрицей инцидентности графа G называется (nґm) –матрица B(G)=[bij], у которой

С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Используя матрицу смежности легко определить локальные степени вершин графа: сумма элементов матрицы по строке равна локальной степени соответствующей вершины. Для орграфов по строке определяются полустепени исхода, по столбцам – полустепени захода.

Пример 72.

Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 25).

Решение.

М атрица смежности имеет вид

.

Поскольку граф не имеет петель, то на главной диагонали стоят все нули. Для любого графа матрица смежности симметрична относительно главной диагонали.

Д ля того, чтобы построить матрицу инцидентности необходимо пронумеровать ребра графа (рис. 26). Матрица инцидентности имеет вид:

Напомним, что в строках указываются вершины, в столбцах – ребра. Матрица инцидентности может быть как квадратной, так и прямоугольной.

Пример 73.

Построить матрицы смежности и инцидентности для  орграфа D= (V, X) (рис. 27).

Решение.

М атрица смежности имеет вид:

Матрица инцидентности имеет вид

29. Графы. Маршруты, пути (определение маршрута; начальная, конечная, внутренняя вершины; подмаршрут, выделенный маршрут, выделенный подпуть, длина маршрута, замкнутый маршрут, цепь, простая цепь, цикл (контур), простой цикл (контур)). Привести примеры. Утверждение о выделении просто цикла (простого контура) и простой цепи.

Маршрут в графе - это последовательность вершин  , такая, что для каждого   вершины   и   соединены ребром. Эти   ребер называются ребрами маршрута. Говорят, что маршрут проходит через них, а число   называют длиной маршрута. Говорят, что маршрут соединяет вершины   и  , они называются соответственно началом и концом маршрута, вершины   называются промежуточными. Маршрут называется замкнутым, если  .

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

Цикл - это замкнутый путь. Цикл   называется простым, если все вершины   попарно различны.

В графе на рисунке 2.1 последовательность вершин

•  - не маршрут;

•  - маршрут, но не путь;

•  - путь, но не простой;

•  - замкнутый маршрут, но не цикл;

•  - цикл, но не простой;

•  - простой цикл.

Рис. 2.1. 

Последовательность ребер графа, в которой любая пара соседних ребер имеет одну и ту же инцидентную вершину, называют маршрутом. В орграфах аналогом маршрута является путь, т.е. такая последовательность дуг, в которой конец одной дуги является началом другой дуги. Маршрут, все ребра которого различны, является цепью, а если различны все вершины, то маршрут — простая цепь. Замкнутая цепь является циклом, замкнутая простая цепь — простым циклом. Цикл, содержащий все ребра графа, называютэйлеровым циклом, а граф, имеющий эйлеров цикл, — графом Эйлера. Простой цикл, который включает все вершины графа, называют гамильтоновым циклом. Для орграфов понятиям цепь и цикл соответствуют понятия путь и контур. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если послед­ ние заданы).

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.