Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 105 стр.

            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2

                                                          Раздел 7. Графы

    На практике часто приходится решать задачи, в которых моделируются
схемы расположения объектов и связей между ними. Например, города – это
объекты, а дороги, их соединяющие, – это связи. Для таких задач удобно ис-
пользовать структуру данных, которая называется графом.
    Граф – это пара множеств V и E, где V – непустое конечное множество то-
чек, называемых вершинами, а E – множество ребер, соединяющих пары вер-
шин.




                             Рис. 7.1 Пример графа.


    На рис. 7.1 представлен граф с множеством вершин {«1», «2», «3», «4»} и
множеством ребер {<1, 2>, <1, 3>, <2, 3>, <3, 4>}.
    Пусть u и v – вершины, а e – ребро, их соединяющее.
    В этом случае вершина u и ребро e называются инцидентными (также как
и вершина v и ребро e). На рис. 7.1 вершина «1» и ребро <1, 2> инцидентны
друг другу. Степень вершины – это число ребер, инцидентных ей, например,
вершина «1» имеет степень 2. Ребра, инцидентные одной вершине, называют-
ся смежными. Вершины, соединенные одним ребром, также называются
смежными. Например, смежными являются вершины «1» и «2», смежными
ребрами являются <1, 3>, <2, 3> и <3, 4>.
    Граф называется полным, если любые две вершины соединены ребром.
Дополнением графа G называется граф G’ с тем же множеством вершин, что
и в G, причем две вершины в G’ смежны тогда и только тогда, когда они не-
смежны в G. Объединение графов G и G’ образуют полный граф. Граф, изоб-
раженный на рис. 7.1, не является полным. Его дополнение изображено на
рис. 7.2.




                                     105