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

Графовые математические модели

Основным плановым документом в системах сетевого планирования и управления ТПП является сетевой график, представляющий собой информационно-динамическую модель, в которой изображаются взаимосвязи и результаты всех работ, необходимых для достижения конечной цели разработки. Кроме того, модель содержит временные, стоимостные и ресурсные характеристики, относящиеся к отдельным работам и всему комплексу. В сетевом графике детально или укрупнено показывается, что, в какой последовательности, когда (за какое время) и для чего необходимо выполнить, чтобы обеспечить окончание всех работ не позже заданного (директивного) срока.

В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде графа.

Графом G называется пара множеств V (G), E (G), где V (G) – непустое конечное множество элементов, называемых вершинами; E (G) – конечное семейство неупорядоченных пар элементов из V (G), называемых ребрами.

Орграфом D называется пара множеств V (D), W (D), где V (D) – непустое конечное множество элементов, называемых вершинами; W (D) – конечное семейство упорядоченных пар элементов из V (D), называемых дугами.

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

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

Две вершины v ₁ и v ₂ называются смежными, если существует соединяющее их ребро; при этом говорят, что вершина v ₁ (либо v ₂) инцидентна этому ребру, и наоборот, ребро инцидентно вершинам v ₁ и v ₂.

Степенью (валентностью) вершины v графа G называется число ребер, инцидентных этой вершине. Во всяком графе число вершин нечетной валентности четно.

Полувалентностью исхода или захода вершины называется число дуг орграфа D, для которых эта вершина является соответственно началом или концом.

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

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

Для любой части P графа G существует единственное дополнение ,состоящее из всех вершин и ребер графа, не принадлежащих P. Отношение между частями P, и графом G можно записать = G – P.

Пусть P₁ и P₂ – две части G. Их сумма представляет собой часть, которая состоит из всех ребер, принадлежащих или P₁, или P₂, или им обеим P _U= P ₁ U P ₂. Аналогично, их пересечение состоит из всех ребер, принадлежащих H ₁и H ₂одновременно. Понятия суммы и пересечения можно распространить на любое количество частей графа.

Маршрутом в графе G называется конечная последовательность ребер вида (v ₀ v ₁), (v ₁ v ₂),..., (v_{m –1} v_m), обозначаемая также как v ₀, v ₁, v ₂, …, v_{m– 1}, v_m. В этой последовательности два соседних ребра либо смежные, либо одинаковые. Каждому маршруту соответствует последовательность вершин: v ₀, v ₁,..., v_m, где v ₀ – начальная вершина (исток I), а v_m – конечная вершина маршрута (сток C). Длиной маршрута называется число ребер в нем. Цепью называется такой маршрут, в котором все его ребра различны. Простой цепью называется цепь, в которой все вершины v ₀, v ₁,..., v_m различны (кроме, может быть, v ₀= v_m). Цепь или простая цепь замкнута, если v ₀= v_m. Циклом называется замкнутая простая цепь, содержащая по крайней мере одно ребро.

Путем в орграфе D называется конечная последовательность дуг вида: (v ₀ v ₁), (v ₁ v ₂),..., (v_{m –1} v_m), обозначаемых также как v ₀, v ₁, v ₂,..., v_{m –1}, v_m.

Нуль-граф – такой граф G, который не имеет ни ребер, ни вершин, V (G) = Æ, E (G) = Æ. Связным графом называется такой граф G, у которого множество ребер E (G) состоит из всевозможных упорядоченных пар вершин из V (G).

Сетью S называется не содержащий циклов орграф D, в котором заданы две вершины: у одной из которых полувалентность захода равна нулю (исток I), а у другой полувалентность исхода равна нулю (сток C), а у остальных вершин множества V (S) полувалентностей исхода и захода отличны от нуля.

Сетевой график – это такая сеть S, у которой вершины V (S) пронумерованы целыми числами, начиная с единицы, а на множестве дуг V (S) заданы весовые коэффициенты.