Лабораторная работа №6 Основные понятия теории графов

Цель работы:

Теоретические сведения

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

Граф может быть задан в форме: G=<X;r>, где r={(x_i;x_j)|x_i,x_jX} (X X)

Граф G=<X;r> называют неориентированным, если (x_i;x_j)=(x_j;x_i), в этом случае отрезок линии (x_i;x_j) называют ребром.

Граф G=<X;r> называют ориентированным, если (x_i;x_j)(x_j;x_i), в этом случае отрезок линии (x_i;x_j) называют дугой.

На рис. 16 приведены неориентированный и ориентированный графы.

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

Граф G=<X;r>, между двумя вершинами которого может быть задано несколько рёбер или дуг, называют мультиграфом.

Для определения отношения принадлежности вершин графа ребру или дуге и, наоборот,рёбер или дуг-вершине вводится понятие “инциденции”, т.е. вершина x_iинцидентна ребру или дуге (x_i;x_j), если она является концевой вершиной данного отрезка линии, а ребро или дуга (x_i;x_j) инцидентна вершине x_i, если отрезок линии ограничен концевой вершиной x_i. Следует обратить внимание, что отношение принадлежности, определяющее понятие “инциденции”, устанавливает связь между элементами двух разных множеств X и r.

Число дуг для ориентированного графа G=<X;r>, исходящих из вершины x_i, называют полустепенью вершины графа и обозначают deg_j(x_i;x_j)⁺. Вершину x_i, инцидентную исходящей дуге (x_i;x_j)⁺, называют вершиной - истоком.

а ) x₁r_1,3x₃ б) x₁r_1,3 x₃

r_0,1r_1,5r_3,5r_0,1r_1,5r_3,5

r_1,4 r_1,4

x₀ x₅ x₀ x₅

r_0,4 r_4,5 r_0,4 r_4,5

x₄ x₄

x₂ x₂

r_4,4 r_4,4

Рис.16. Неориентированный (а) и ориентированный (б) графы.

Две вершины графа называются смежными, если они различны и между ними существует ребро или дуга.

Вершина x_i, несмежная ни с одной вершиной графа, называется изолированной. На рис.16 изолированной является вершина x₂ .

Два ребра также называются смежными, если они различны и имеют общую вершину.

Последовательность смежных рёбер или дуг, соединяющих вершины x_iи x_j, называют маршрутом и обозначают M_j=((x_i,x_k);…. . . (x_l;x_j)). Например, для графа на рис.16а) между вершинами x₀ и x₅ существует шесть маршрутов, т.е.

M_0;5={(r_0;4;r_4;5);(r_0;1;r_1;4;r_4;5);(r_0;1;r_1;5);(r_0;4;r_4;1;r_1;5);(r_0;4;r_4;1;r_1;3;r_3;5); (r_0;1;r_1;3;r_3;5)}.

Маршрут неориентированного графа G=<X;r>, связывающий вершины x_iи x_j, называют цепью.

Маршрут ориентированного графа G=<X;r>, связывающий вершины x_iи x_j, называют путём.

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

Маршрут называют открытым, если его концевые вершины различны, и замкнутым, если его концевые вершины совпадают.

Замкнутый маршрут для неориентированного графа называют циклом, а для ориентированного графа - контуром.

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

Маршрут называют гамильтоновым, если он замкнут и проходит через каждую вершину графа только по одному разу.

Длина маршрута равна числу смежных рёбер, соединяющих вершины x_iи x_j

Длину минимального маршрута, соединяющего вершины x_iи x_jназывают расстоянием. Так расстояние между вершинами x₀ и x₅ графа, приведённого на рис.16а), равно 2.

Замкнутый маршрут, который содержит только одно ребро или дугу (длина маршрута равна 1), называют петлёй. На рис.16 петля указана для вершины x₄.

Если ребро или дуга обладают дополнительной характеристикой - протяжённостью l_k,l, то длина маршрута равна сумме длин рёбер или дуг, его составляющих.

Если ребро или дуга обладают дополнительной характеристикой - пропускной способностью, то пропускная способность маршрута равна минимальной пропускной способности для множества рёбер или дуг, его составляющих.

Граф G=<X;r> называют связным, если любые две его вершины можно соединить цепью. Для ориентированного графа выделяют сильную связность, когда любые две его вершины взаимодостижимы при наличии дуг, и слабую связность, когда любые две его вершины достижимы только при условии замены дуг на рёбра.

Граф G=<X;r> называют полным, если любые две его вершины смежны между собой (см. рис.17а)).

Граф G=<X;r> называют пустым, если любые две его вершины не смежны между собой (см. рис.17б)).

Граф G=<X;r> называют дополнительным для графа G=<X;r>, если он опирается на множество вершин графа G, которые смежны для графа G только в случае их несмежности в графе G, т.е. r=r. Так пустой граф (см. рис.17б)) есть дополнительный для полного графа (см. рис.17а)).

Граф G=<X;r> называют деревом, если он связный, но без циклов, петель и кратных рёбер или дуг (см. рис.18а)).

Граф G=<X;r> называют лесом, если он несвязный и без циклов, петель и кратных рёбер или дуг.

Расстояние от вершины x_iдля графа типа дерево до наиболее удалённой вершины x_jназывают эксцентриситетом графа и обозначают e _i.

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

Следует обратить внимание, что в связном графе типа дерево число рёбер всегда равно (n-1), где n - число вершин графа.

x₁ x₁

а) б)

x₃ x₂ x₅ x₂

x₄ x₃ x₄ x₃

Рис. 17. Полный (а) и пустой (б) графы.

а ) диаметр б)

6 эксцентриситет 7 3 3

5 центроид 6 2 2

6 4 5 2 2 2

центр

7 4 6 3 3

1

5 5 2 2

Рис. 18. Граф типа дерево (а) и лес (б).

Граф может быть задан для анализа с помощью таблиц или матриц.

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

Матрица инциденции. Поскольку инциденция есть отношение принадлежности элемента одного множества X другому множеству r, то матрица инциденции ||h_i;j|| есть прямоугольная, число строк которой равно мощности множества |r|=m, а число столбцов - мощности множества |X|=n. Элементы матрицы инциденции для неориентированного графа определяются соотношением:

1, если ребро r_i;jинцидентно вершинам x_iи x_j;

h_i;j^X=

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

Таблица 9.

равно степени вершины, т.е. deg_i, поэтому для последующего анализа желательно выделить строку, раскрывающую степени вершин графа.

Элементы матрицы инциденции для ориентированного графа определяются другим соотношением:

h_i;j= 0, если дуга r_i,j не инцидентна вершинам x_iи x_j;

-1, если дуга r_i,j заходит в вершину x_j.

В таблице 10 представлена матрица инциденции для ориентированного графа (см. рис. 16б)). Также можно отметить, что в каждой строке сумма “+1” и “-1” равна двум, что характеризует наличие для отрезка линии, представляющего дугу, одной вершины - истока и одной вершины - стока.

В каждом столбце матрицы инциденции число “+1” равно полустепени исхода вершины x_i, т.е. deg_i⁺, а число “-1” равно полустепени захода вершины x_i, т.е. deg_i^-.

Матрица смежности. Поскольку смежность есть бинарное отношение между элементами одного множества, то матрица смежности ||r_i,j|| есть квадратная матрица, число строк и столбцов которой равно мощности множества |X|=n.

Элементы матрицы смежности определяются соотношением:

1, если вершина x_i смежна вершине x_j;

r_i,j=

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

В таблице 11 представлена матрица смежности для неориентированного графа (см. рис. 16а)). Элементы матрицы смежности, равные 1, расположены симметрично относительно главной диагонали. В каждой строке и в каждом столбце такой матрицы число “1” равно степени вершины, т.е. deg_i. Поэтому можно выделить дополнительную строку или столбец для хранения информации о степени каждой вершины графа.

Таблица 11.

В таблице 12 представлена матрица смежности для ориентированного графа (см. рис. 16б)), но при условии, что строки заданы вершинами-истоками графа, а столбцы - вершинами-стоками. Поэтому итоговый столбец таблицы- _i⁺ показывает полустепень каждой вершины-истока, а итоговая строка- _I^- - полустепень каждой вершины-стока.

По структуре матрицы смежности можно сделать выводы:

1. каждый ненулевой элемент главной диагонали соответствует петле на графе;

2. матрица смежности для неориентированного графа симметрична относительно главной диагонали;

3. матрица смежности для ориентированного графа несимметрична относительно главной диагонали;

Матрица весов. Протяжённость ребра или дуги, а также затраты времени, энергии или финансов на перемещение пакета информации или транспортной единицы по ребру или дуге из вершины x_iв вершину x_jформирует рёберно-взвешенный граф.

Элементы матрицы весов рёберно-взвешенного графа определяются соотношением:

r_i,j=

l_i,j, если вершина x_iсмежна вершине x_jи вес ребраl_i,j;

, если вершина x_iнесмежна вершине x_j.

Задания

1. Ориентированный граф G=(V,E,O) задан аналитическим способом. Необходимо:

1. задать граф геометрическим способом;

2. определить полустепени вершин графа;

3. определить матрицу смежности

4. определить матрицу инцидентности

Для проверки решения использовать программу Grin

Варианты:

1. V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₁), (v₁,v₃), (v₁,v₅), (v₂,v₃), (v₂,v₄), (v₂,v₅), (v₃,v₃), (v₃,v₄), (v₄,v₅), (v₅,v₅)).

2. V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀,e₁₁), O = ((v₁,v₂), (v₁,v₃), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₃), (v₂,v₅), (v₃,v₃), (v₃,v₄), (v₄,v₄), (v₄,v₅)).

3. V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₂), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₃), (v₂,v₅), (v₃,v₄), (v₃,v₅), (v₄,v₄), (v₅,v₅)).

4. V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₂), (v₁,v₃), (v₂,v₂), (v₂,v₄), (v₂,v₅), (v₃,v₄), (v₃,v₅), (v₄,v₄), (v₄,v₅), (v₅,v₅)).

5. V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀,e₁₁), O = ((v₁,v₁), (v₁,v₃), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₄), (v₂,v₅), (v₃,v₃), (v₃,v₅), (v₄,v₄), (v₄,v₅)).

6. V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₃), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃), (v₃,v₅), (v₄,v₄), (v₅,v₅)).

7. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₁), (v₁,v₃), (v₁,v₂), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₃,v₄)).

8. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆, e₇,e₈ ), O = ((v₁,v₁), (v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃)).

9. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₄,v₃)).

10. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇), O = ((v₁,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃), (v₄,v₁), (v₄,v₄), (v₃,v₄)).

11. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₂), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁))

12. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₂), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁)).

13. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₁), (v₁,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁)).

14. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₃), (v₁,v₂), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₃,v₄), (v₄,v₃)).

15. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₁), (v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃)).

16. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆, e₇,e₈ ), O = ((v₁,v₁), (v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃)).

17. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₄,v₃)).

18. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇), O = ((v₁,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃), (v₄,v₁), (v₄,v₄), (v₃,v₄)).

19. V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₂), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁))