Главная Обратная связь

Дисциплины:






Способы задания графов



 

Граф можно задать аналитически как совокупность множества вершин V и множества ребер U:G=<V,U>, где V={V1,V2,…,VN}, U={U1, U2, …, UR}. Однако более наглядными являются графические способы задания графов.

Матрица инцидентности – это прямоугольная матрица I размерностью N x R, имеющая N строк и R столбцов, и определяющая инцидентность вершин и ребер графа:

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

 

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

I(i,j) =

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

 

В каждом столбце матрицы инцидентности ровно две единицы. У ориентированного графа I(i,j)=±1, в зависимости от направления дуги. Для записи информации об инцидентности вершин и ребер графа используется также список концов ребер, т.е. для каждого ребра задается пара его конечных вершин. Для орграфа первой указывается вершина, из которой выходит дуга.

Матрица смежности – это квадратная матрица размерностью N x N, элементы которой определяются так:

1, если Vi и Vj смежны,

S(i,j) =

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

 

Для неориентированного графа матрица смежности S симметрична, для орграфа S(i,j)=1, если есть дуга от Vi к Vj. В случае мультиграфа в качестве S(i,j) задается кратность соответствующего ребра или его вес.

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

На рис.1 приведены примеры задания орграфа.


 


Связность в графах

 

Орграф называется сильносвязанным, если для любых двух вершин Vi и Vj найдется путь из Vi в Vj, и наоборот путь из Vj в Vi . В противном случае граф называется несвязным.

На рис. 2 показаны сильносвязный и несильносвязный графы.

V3
V2
V1

 

Рис.2

Компонентой сильной связности орграфа G называется его подграф G`, удовлетворяющий следующим условиям:

1) подграф G` - сильносвязный;

2) добавление к G` любой вершины Vi из графа G c дугами инцидентности V нарушает условие сильной связности подграфа G`.

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

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

Прямым транзитивным замыканием вершины Vi орграфа называется выражение



где - множество вершин графа, в которые ведут дуги из вершины Vi;

- множество вершин графа, в которые ведут дуги из множества вершин ;

- множество вершин графа, в которые ведут дуги из множества вершин , т.д.

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

Обратным транзитивным замыканием вершины Vi орграфа называется выражение

где - множество вершин графа, из которых идут дуги в вершину Vi и т.д.

Если для вершины Vi найдены и , то компонента сильной связности, включая вершину Vi ,может быть найдена так:

.


1.3.1 Алгоритм нахождения компонент сильной связности (алгоритм Мальгранжа-Томеску)

1) Граф задается матрицей смежности (рис.3).

       
   
 
 
 
 

 

 

 


2) Матрица смежности дополняется столбцом и строкой , где Vi выбирается крайним слева среди столбцов. Переходят к алгоритму заполнения столбца.

3) Если столбец заполнен, переходят к алгоритму заполнения строки .

Алгоритм заполнения строки аналогичен алгоритму заполнения столбца.

4) Находят

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

 

1.3.2 Алгоритм заполнения столбца .

1) В клетке столбца , являющейся продолжением строки Vi матрицы смежности, ставится нуль. Переход к п.2.

2) Если в клетках матрицы смежности на пересечении i-ой строки и столбцов Vj,…,Vk стоят единицы, то в клетках столбца , являющихся продолжением строк Vj,…,Vk ставятся единицы. Переход к п.3.

3) Если в клетках матрицы смежности на пересечении строк Vj,…,Vk со столбцами Vp,…,Vm стоят единицы , то в клетках столбца являющихся продолжением строк Vj,…,Vk ставится цифра 2. Переход к п.4.

4) Процесс заполнения столбца продолжается до тех пор, пока возможно. Переход к п.5.

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

Пример

Задана матрица смежности графа. Найти разложение графа на компоненты сильной связности.

На рис.4 показана матрица смежности графа и заполнение столбца и строки , которым соответствует прямое и обратное транзитивное замыкание: ={1,2,3,4,5}, ={1,2,3} и компонента сильной связности ={1,2,3}. После вычеркивания столбцов и строк матрицы смежности с номерами 1,2,3, вошедшими в , рассматривается остаток матрицы, столбец и строка заполняются. В результате получается прямое и обратное транзитивное замыкание и компонента сильной связности: ={4,5}, ={4,5}, ={4,5}.

           
                   
                     
                 
                   
                 
              x   x  
              x   x  

 

x X x x
               
      x x
               
         

Рис.4

Рассмотрение элементов матрицы, оставшихся после вычеркивания столбцов и строк с номерами 4 и 5 дает такие результаты: ={6,7}, ={6,7}, ={6,7}.

Таким образом, представленный граф имеет 3 компоненты сильной связности: , , .

 

Раскраска графа

 

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

Если необходимо раскрасить вершину Vj графа, смежную с вершинами Vk,Vl,Vm, уже выкрашенными в цвета с номерами 0,1,3, то вершина Vj красится в цвет, номер которого минимален и не равен номерам цветов вершин, смежных с Vj. В рассмотренном примере вершину Vj нужно покрасить в цвет 2. Вышеизложенное определяет смысл функции Гранди, а общий алгоритм раскраски графа с ее помощью состоит в следующем:

1) на графе выбирают произвольную вершину и окрашивают в цвет, номер которого минимален;

2) выбирают вершину, смежную с окрашенной, и красят ее в цвет, номер которого минимален и не равен номеру цвета окрашенной вершины;

3) находят вершину графа, смежную с окрашенными, и красят ее в цвет, номер которого минимален и не равен номерам окрашенных вершин;

4) если смежных вершин нет, возвращаются к п.1, в противном случае конец.

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

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

 





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...