Тема 4.Графы

1. Основные понятия и определения

Графсостоит из множества узлови множества дуг. Каждая дуга в графе указывается парой узлов. Примеры графов:

Граф G1 Граф G2

Для графа G1 множество узлов – {A,B,C,D,E,F,G,H}, множество дуг – {(A,B), (A,D), (A,C), (C,D), (C,F), (E,G), (A,A)}. Дуга, соединяющая узел с самим собой, называетсяпетлей. Узел может не иметь связанных с ним дуг (узелHграфаG2). Если пары узлов, образующих дугу, упорядочены, то граф называюториентированным, илинаправленным, графом(графG2 – ориентированный); дуги в этом случае изображают стрелками. В этой теме мы будем рассматривать только ориентированные графы без петель.

Узел nназываетсяинцидентнымдугеx, еслиn– это один из двух узлов упорядоченной пары, составляющей дугуx(говорят также, что дугаxинцидентна узлуn).Степень узла– это число дуг, инцидентных узлу.Полустепень заходаузла – это число дуг, входящих в узел, аполустепень исходаузла – это число дуг, выходящих из узла. Например, узелCграфаG2 имеет полустепень захода 2, полустепень исхода 1 и степень 3. Узелnназываетсясмежнымс узломm, если существует дуга изmвn.

Часть графа– это граф, содержащий часть узлов исходного графа и часть (любую) его дуг.

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

Суграфсодержит все узлы исходного графа и часть его дуг.

Граф Часть графа Подграф Суграф

G3 G4 G5 G6

Граф называется полным, если любые два его различных узла соединены дугой. Например, графыG3 иG5 полные.

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

С каждой дугой графа может быть связано некоторое значение, как в графе G2. Такой граф называетсявзвешеннымграфом, а связанное с каждой дугой значение называетсявесом.

Путьот узлаaдо узлаb– это последовательность узловn₀,n₁, ...,n_k, такая, чтоn₀=a,n_k=bи для любогоiот 0 доk-1 узелn_i+1смежен узлуn_i, т.е. существует дуга изn_iвn_i+1. Длина путиn₀,n₁, ...,n_kравна количеству его дуг, то естьk. Например, в графеG7 путьA,B,C,Dимеет длину 3 и соединяет узлыAиD.

Граф g7

Длина пути во взвешенном графе равна сумме весов дуг, входящих в этот путь.

Путь, не содержащий одинаковых узлов (за исключением, может быть, n₀=n_k), называется простым.

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

Расстояниемежду двумя узлами – это длина кратчайшего пути, соединяющего эти узлы.

Граф называется связным, если для любой пары узлов существует соединяющий их путь. Например, графG3 связный, а графыG4 –G6 – нет. Очевидно, что ориентированный граф не будет связным, если в нем есть узлы, не имеющие входящих или исходящих дуг. Неориентированный граф несвязный, если он содержит узлы, не имеющие инцидентных с ним дуг.

Связный ориентированный граф без петель называется сетью.

2. Операции над графом

Над графом g могут быть выполнены следующие операции:

– возвращение адреса узла со значением v–NodeAddr(g,v);

– проверка смежности узлов Node1иNode2 –ArcAddr(g,Node1,Node2);

– возвращение начального узла дуги Arc–HeadNode(g,Arc);

– возвращение конечного узла дуги Arc–RearNode(g,Arc);

– возвращение информации, содержащейся в узле, – Value(g,Node);

– проверка наличия узлов в графе – Empty(g);

– включение дуги между узлами Node1 и Node2 – AddArc(g, Node1, Node2);

– исключение дуги между узлами Node1 и Node2– DeleteArc(g, Node1, Node2);

– включение узла со значением vв граф –AddNode(g,v);

– исключение из графа узла Nodeс исключением инцидентных ему дуг и возвращение значения информационного поля узла –DeleteNode(g,Node);

– определение количества узлов в графе – NodesQuantity(g);

– просмотр графа – Revision(g);

– создание пустого графа – Create(g);

– удаление всех узлов и дуг графа – Clear(g);

– построение графа – Build(g).

С использованием вышеперечисленных операций можно реализовать более сложные операции: определение расстояния (кратчайшего пути) между двумя заданными узлами графа; поиск узлов в графе; определение путей между двумя заданными узлами графа и их длин и др.

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