Основные понятия. Графические представления в широком смысле - любые наглядные отображения исследуемой системы, процесса

Теория графов

Графические представления в широком смысле - любые наглядные отображения исследуемой системы, процесса, явления на плоскости. К ним могут быть отнесены рисунки, чертежи, графики зависимостей характеристик, планы-кар­ты местностей, блок-схемы процессов, диаграммы и т.п. Такие изображения наглядно представляют различные вза­имосвязи, взаимообусловленности: топологическое (про­странственное) расположение объектов, хронологические (временные) зависимости процессов и явлений, логические, структурные, причинно-следственные (каузальные) и другие взаимосвязи.

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

Рисунок 2.1

Рисунок 2.2

Все более распространенными становятся представления количественных характеристик, взаимосвязей между объек­тами в виде разного рода одно-, двух- и более мерных гисто­грамм (рисунок 2.1), круговых диаграмм (рисунок 2.2), других аналогичных способов представления в виде тех или иных гео­метрических фигур, по наглядным характеристикам которых (высоте, ширине, площади, радиусу и пр.) можно судить о ко­личественных соотношениях сравниваемых объектов, значи­тельно упрощая их анализ.

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

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

Графические представления в узком смысле - это описа­ние исследуемой системы, процесса, явления средствами те­ории графов в виде совокупности двух классов объектов: вершин и соединяющих их линий -ребер или дуг. Графы и их составляющие характеризуются определенными свойства­ми и набором допустимых преобразований (операций) над ними.

Графом G называется совокупность двух множеств: вер­шин V и ребер Е, между элементами которых определено отношение инцидентности — кажде ребро ееЕ инциден­тно ровно двум вершинам v', v" V, которые оно соединя­ет. При этом вершина v' (v") и ребро е называются инци­дентными друг другу, а вершины v' и v", являющиеся для ребра е концевыми точками, называются смежными. Часто вместо v V и е Е пишут соответственно v G, е G.

Рис. 2.3.

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

Граф, содержащий направленные ребра (дуги) с нача­лом v' и концом v", называется ориентированным (орграфом), а ненаправленные - неориентированным (назовем н-графом).

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

Граф называется конечным, если множество его элемен­тов (вершин и ребер) конечно, и пустым, если его множе­ство вершин F(a значит и ребер Е) пусто. Граф без петель и кратных ребер именуется полным, если каждая пара вершин соединена ребром.

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

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

Локальной степенью (или просто степенью) вершины v V н-графа G называется количество ребер (v), инци­дентных вершине v. В н-графе сумма степеней всех вер­шин равна удвоенному числу ребер т графа, т.е. четна (предполагается, что в графе с петлями петля дает вклад 2 в степень вершины):

отсюда следует, что в н-графе число вершин нечетной степени четно.

Для вершин орграфа определяются две локальные сте­пени:

• ₁ (v) –число ребер с началом в вершине v, или количество выходящих из v ребер;

• ₂ (v) – количество входящих в v ребер, для которых эта вершина является концом.

Петля дает вклад 1 в обе эти степени.

В орграфе суммы степеней всех вершин ₁(v) и ₂(v) равны количеству ребер т этого графа, а значит, и равны между собой:

Графы G₁ и G₂ равны, т.е. G₁ = G₂, если их множе­ства вершин и ребер (выраженных через пары инциден­тных им вершин) совпадают: V₁ = V₂ и Е₁= Е₂ Графы G₁ и G₂ на рисунке 2.3 равны. Граф G считается полностью заданным в строгом смысле, если нумерация его вер­шин и ребер зафиксирована. Графы, отличающиеся только нумерацией вершин и ребер, называются изомор­фными.

Пример 1. Задать граф G₁ представ­ленный на рисунке 2.4, через множества вер­шин V₁ и ребер Е_1.

Граф G₁ может быть полностью определен:

1) двумя множествами поименованных вершин V₁ = {v₁, v₂, v₃, v₄, v₅} и поименованных ребер E₁ = {e_1, е₂, е₃, е₄} (в строгом смысле требуется установление от­ношения инцидентности ребер соответствующим вершинам);

Рисунок 2.4

2) множеством ребер, каждое из которых представлено па­рой своих концевых вершин: Е₁= {(v₁ v₄), (v₄, v₃), (v₃, v₅), (v₅,v₂)}.

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

Пример 2. На рисунке 2.5 изображены графы G₁- G₁₂ с четырьмя вершинами в каждом. Сравнить графы.

Рисунок 2.5

Результаты сравнения графов таковы:

G₁-G₇- неориентированные; G₈- G₁₂ - ориентирован­ные;

G₁,G₂- полные, причем G₁ = G₂;

G₇ - не является полным, так как хотя каждая пара вер­шин и соединена ребром, но имеется одна петля. (Иногда полным называют граф с петлями во всех вершинах, каждая пара которых соединена ребром. Граф G₇ не отвечает и этому определению.

G₃ - все вершины этого графа являются изолированными (граф с пустым множеством ребер);

G₄ и G₅ являются дополнением друг другу: G₄ = и G₅ = ;

G₆ - мультиграф, так как содержит кратные ребра а и b, а также е и f;

G₈ - ориентированный, канонически соответствующий неориентированному графу G₅;

G₉ и G₁₀ не являются равными, так как имеют отличающиеся ребра: (4, 1) – в G₉ и (1,4) –b G₁₀;

G₁₁ - ориентированный мультиграф: ребра а и b – кратные, тогда как G₁₂ мультиграфом не является, поскольку в нем ребра а и bразлично ориентированы.

Пример 3. Чему равны степени вершин графов G₁ иG₃ на рисунке 2.6?

Рисунок 2.6

Оба графа имеют по четыре вершины: V= { 1,2,3,4}.

Степени вершин неориентированного графа G₁: (1) = 3, (2) = 4, (3) = 3, (4) = 4, если условиться считать вклад петли в степень вершины, равный 2, и (4) = 3, если петля дает вклад 1 в степень вершины. Сумма степеней всех вер­шин графа G₁ равна 14, т.е. вдвое больше числа ребер графа:

14=2m,

где т = 7 - число ребер графа.

Степени вершин ориентированного графа G₃:

₁(l) = 2, ₁ (2) = 3, ₁ (3)=l, ₁(4)=l;

₂(l)=l, ₂(3)=l, ₂(3) = 2, ₂(4) = 3.

Суммы степеней вершин первого и второго типа графа G₃ совпадают и равны числу т ребер графа:

7=m.