Матричное задание графов. Матрица смежности и инцидентности.

Пусть D-орграф, где V={v₁,v₂,…,v_n}, X={x₁,x₂,…,x_n}. Матрицей смежности орграфа D называется матрица A(D)=[a_ij] порядка n, у которой:

1, (v_i,v_j)  x

0, (v_i,v_j)  x

Матрицей инцидентности орграфа D называется матрица (n  m) B(D)=[b_ij] , у которой:

1, если вершина v_i является концом дуги x_j

-1, если v_i является началом дуги x_j

0, если v_i не инцидентна дуге x_j

Вспомогательный рисунок №2 на рис 1.2 показан пример матричного задания орграфа.

Пусть G(V, X) граф, где V={v₁,v₂,…,v_n}, X={x₁,x₂,…,x_n}. Матрицей смежности графа G называется матрица A(G)=[a_ij] порядка n, у которой:

1, (v_i,v_j)  x

0, (v_i,v_j)  x

Матрицей инцидентности графа G называется матрица (n  m) B(G)=[b_ij], у которой:

1, если вершина v_i инцидентна ребру x_j

0, если v_i не инцидентна x_j

Вспомогательный рисунок №2 на рис 1.1 показан пример матричного задания графа.

Связанность. Компоненты связанности.

Говорят, что вершина w орграфа D ( гр. G ) достижима из вершины v, если либо w = v, либо существует путь из v в w (маршрут из v в w ). Говорят, что граф связан (оргр. сильно связанный ), если для его вершин v, w существует маршрут ( путь ), соединяющий эти вершины. Оргр. называется односторонне цельно связанным, если для его вершин по крайней мере одна достижима из другой.

Матрица связанности: пусть D=(V, X) орграф, где V={v₁,…,v_n}. Матрицей достижимости называется квадратная матрица T(D)=[t_ij] порядка n, у которой t_ij=1, если вершина v_j достижима из v_i, t_ij=0 в противном случае.

Матрицей сильной связанности орграфа D называется квадратная матрица S(D)=[s_ij] порядка n, у которой s_ij=1, если вершина v_i достижима из v_j и одновременно v_jдостижима из v_i, s_ij=0 в противном случае. Пусть G=(V, X) граф. Матрицей связанности графа G называется квадратная матрица S(G)=[s_ij] порядка n, у которой s_ij=1, если j = i или существует маршрут соединяющий v_i и v_j, s_ij=0 в противном случае.

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

Алгоритм Терри: (алгоритм поиска маршрута в связанном графе G, соединяющего заданные вершины v и w  V, где v ≠ w.)

Шаг1: идя по произвольному ребру, всякий раз отмечать направление, которое оно прошло.

Шаг2: исходя из некоторой v^' , всегда следовать только по тому ребру, которое не было пройдено или было пройдено в противоположном направлении.

Шаг3: для всякой вершины v^', отличной от v отмечать первое заходящее в v^' ребро, если v^' встречается первый раз.

Шаг4: исходя из некоторой вершины v^', отличной от v по первому заходящему ребру идти лишь тогда, когда нет других возможностей.

Так же существуют задачи на нахождение маршрута.

 

Деревья и циклы

Граф G называется деревом, если он является связанным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

Свойства деревьев.

Следующие утверждения эквивалентны:

1. граф G есть дерево;

2. граф G является связным и не имеет простых циклов;

3. граф G является связным и число его ребер равно на единицу меньше числа вершин;

4. Любые две различные вершины графа G можно соединить единственной (и при этом простой) цепью;

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

Утверждение. Если у дерева G есть по крайней мере, одно ребро, то у него обязательно найдется висячая вершина.

Утверждение. Пусть G-связный граф, v – висячая вершина в G, G^' – граф полученный из G в результате удаления вершины v и инцидентного ей ребра. Тогда G^' - связный граф.

Утверждение. Пусть G – дерево с n вершинами и m ребрами. Тогда m= n – 1.

Утверждение. Пусть G^' -- граф являющийся деревом, G- граф полученный в результате добавления к G^' новой вершины v и ребра {v, W} где W -- некоторая вершина графа G^'. Тогда G - дерево.

Утверждение. Пусть G = (v, X) – связный граф с n ребрами и m вершинами и пусть так же выполняется равенство m = n –1. Тогда G – дерево.

Утверждение. Пусть G – дерево. Тогда любая цель в G будет простой.