Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов

Страницы работы

47 страниц (Word-файл)

Содержание работы

3. Основы теории графов

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

          Первая работа по теории графов была опубликована математиком Л. Эйлером в 1736г. в Трудах Академии наук Санкт-Петербурга в виде задачи о Кенигсбергских мостах (см. рис. 9). Суть задачи сводилась к следующему: мог ли житель Кенигсберга, выйдя из дома, находящегося на части суши A, B, С или D, пройти по семи мостам через реку Прегель в точности по одному разу и вернуться домой? Ответ на этот вопрос был отрицательным.

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

3.1. Граф и его характеристики

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

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

Граф может быть задан в двух формах:

а) G=<X, r>,

   где r={(xi, xj)| xi, xjÎX}Í(XÄX)  или

б) G=<X; h>,

   где h={{xj}Xi| xi, xj ÎX}Í(XÄX).

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

Граф G=<X; r> называют неориентированным, если (xi, xj)=(xj, xi).

Отрезок линии (xi; xj), соединяющий две вершины, называют ребром.

Граф G=<X; r> называют ориентированным, если (xi, xj)¹(xj, xi), а направленный отрезок линии (xi; xj), соединяющий две вершины,  называют дугой.   На рис. 10 приведены неориентированный и ориентированный графы.

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

Для определения отношения принадлежности вершин графа ребру или дуге и, наоборот, рёбер или дуг - вершине вводится понятие “инциденция”, т.е. вершина xинцидентна ребру или дуге (xi, xj), если она является концевой вершиной данного отрезка линии, а ребро или дуга (xi, xj) инцидентна вершине xi , если отрезок линии ограничен концевой вершиной xi .

Число вершин, инцидентных ребру или дуге, всегда равно 2, т.к. они являются концевыми вершинами отрезка линии, а число рёбер или дуг, инцидентных вершине xi, может быть произвольным. Это число называют степенью или валентностью вершины xi и обозначают di=Sj(xi, xj). Число дуг, исходящих из вершины xi, называют полустепенью вершины графа и обозначают di+=Sj(xi, xj)+. Вершину xi, инцидентную исходящей дуге (xi, xj)+,  называют истоком( символ ”+” cвидетельствует о направлении дуги от вершины xi). Число дуг, заходящих в вершину xi, также называют полустепенью вершины графа и обозначают di-=Sj(xi, xj)-. Вершину xi, инцидентную заходящей дуге (xj, xi)-  , называют стоком ( символ ”-” cвидетельствует о направлении дуги к вершине xi).

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

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

Последовательность смежных рёбер или дуг, соединяющих вершины xi и xj , называют маршрутом и обозначают mij=((xi, xk);…. . . (xl, xj)). Например, для неориентированного графа, приведенного на рис. 10, между вершинами x0 и x5 существует шесть маршрутов, т.е. m05={(r04, r45); (r01, r14, r45); (r01, r1,5); (r04, r41, r15); (r04, r41, r13, r35); (r01, r13, r35)}.

Похожие материалы

Информация о работе