Тема: Сетевые модели (стр. 1 )

РГР

Тема: Сетевые модели.

Цель работы

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

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

Основные понятия теории графов

Граф G—это совокупность двух конечных множеств: множества точек, которые называются вершинами, и мно­жества пар вершин, которые называются ребрами.

На рис. 1.1 изображен граф, имеющий пять вершин и шесть ребер.

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

Ребра, имеющие одинаковые концевые вершины, назы­ваются параллельными.

Ребро, концевые вершины которого совпадают, назы­вается петлей. На рис. 11.1и – параллельные ребра, а – петля.

Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. На рис. 11.1 вершинаи ребро инцидентны друг другу.

Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Два ребра, инци­дентные одной и той же вершине, называются смежными ребрами. На рис. 1.1 – смежные вершины, – смежные ребра,

Степенью вершины называется число ребер, инцидент­ных ей. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной. На рис. 1.1 степень вершины равна трем, – висячая вершина, – изо­лированная.

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

Дополнением графа G называется граф с теми же вершинами, что и граф G, и содержащий только те ребра, которые нужно добавить к графу G, чтобы получился полный граф. На рис. 1.2 изображены следующие графы: G1 –полный граф с пятью вершинами, G2 – некоторый граф, имеющий пять вершин, – дополнение графа G2.

Путем в графе называется такая последовательность ребер, ведущая от некоторой начальной вершины p1 в ко­нечную вершину pn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Например, в графе, изображенном на рис, 1.1, последовательность реберобразует путь, ведущий от вершины p1 к вершине р4.

Циклом называется путь, начальная и конечная вер­шины которого совпадают. На рис. 11.1 ребра образуют цикл.

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

Длиной пути или цикла называется число ребер этого пути или цикла.

Связные графы

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

Любой несвязный граф является совокупностью связ­ных графов. Эти графы обладают тем свойством, что никакая вершина одного из них не связана путем ни с какой вершиной другого. Каждый из этих графов называется компонентой графа G. На рис. 1.3 изображен несвязный граф G с компонентами G1,G2,G3. Каждая компонента являет­ся связным графом.

Деревья и лела

Связный граф, не содержащий циклов, называется деревом.

Деревом некоторого графа G называется его связный подграф без циклов. Дерево графа G, содержащее все его вершины, называется остовом графа G или его покрыва­ющим деревом.

Кодеревом T* остова Т графа G называется такой под­граф G', который содержит все его вершины и только те ребра, которые не входят в T.

Ребра остова Т называются ветвями графа G, а ребра кодерева – Т* –связями.

Граф, не содержащий циклов и состоящий из k компонент, называется к-деревом; к-дерево графа G, содержа­щее все его вершины, называется остовным.

Подграф G, содержащий все его вершины и только те ребра, которые не входят в остовное k-дерево Т графа G, называется k-кодеревом Т*.

Если граф G содержит k компонент, то его остов­ное k-дерево Т называется лесом, а k-кодерево Т* в этом случае называется КО-лесом.

Рангом графа G, имеющего n вершин и состоящего из k компонент, называется число r(G) = n - k.

Цикломатическим числом графа называется число где m –число ребер графа G.

Очевидно, что ранг и цикломатическое число связаны следующим соотношением:

Эйлеровы и гамильтоновы графы

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

Граф, обладающий эйлеровым циклом, называется эй­леровым графом.

На рис. 1.9 граф G не является эйлеровым, так как вершина р3 инцидентна только одному ребру.

Если путь приведет в вершину p3 то не будет ребра, по которому можно было бы выйти из p3.

Граф G, изображенный на рис. 1.10, является эйле­ровым. Последовательность ребер, образует эйлеров цикл.

На рис. 1.9 изображен граф G, обладающий эйлеро­вым путем с концевыми вершинами p5 и p3.

Гамильтоновым путем (циклом) графа G называется путь (цикл), проходящий через каждую вершину G в точ­ности по одному разу

Граф, обладающий гамильтоновым циклом, называется гамильтоновым.

Критерий существования гамильтонова цикла в произ­вольном графе G еще не найден. Достаточным условием существования гамильтонова цикла является полнота графа G.

Граф, изображенный на рис. 1.9, не является гамиль­тоновым, а граф, представленный на рис. 1.11, содер­жит гамильтонов цикл

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

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

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

В ориентированных графах циклом называется путь, начало и конец которого совпадают. На рис. 1.12 дуги образуют цепь, а дуги − путь. Последовательность дуг составляет цикл, а последовательность не является циклом.

Цепь, путь, цикл в произвольном графе G называются простыми, если они не проходят ни через одну свою вер­шину более одного раза. Длиной цепи, пути, цикла называется число содержа­щихся в них дуг.

Сетью называется граф, каждой дуге которого постав­лено в соответствие некоторое число (или несколько чисел).

Многие практические задачи могут быть решены е по­мощью теории графов. Рассмотрим некоторые примеры.

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

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

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