Графические представления – удобный способ иллюстрации содержания различных понятий, относящихся к другим способам формализованных представлений (диаграммы Венна).
Все более распространенными становятся представления количественных характеристик, взаимосвязей между объектами в виде разного рода гистограмм, круговых диаграмм, по наглядным характеристикам которых можно судить о количественных соотношениях сравниваемых объектов, значительно упрощая их анализ.
Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются так называемые графы. Теория графов имеет огромные приложения, так как ее язык, с одной стороны нагляден и понятен, а с другой стороны – удобен в формальном исследовании. На языке теории графов формализуются и решаются многие задачи, в том числе задачи сетевого планирования и управления, анализа и проектирования организационных структур управления, анализа процессов функционирования и целеполагания, многие задачи принятия решений в условиях неопределенности и др.
Графическое представление в другом смысле – это описание исследуемой системы, процесса, явления средствами теории графов в виде совокупности двух классов объектов: вершин и соединяющих их линий – ребер или дуг. Графы и их составляющие характеризуются определенными свойствами и набором допустимых преобразований (операций) над ними.
Графом G называется совокупность двух множеств – вершин V и ребер Е между элементами которых определено отношение инцидентности – каждое ребро ℓÎЕ инцидентно равно двум вершинам u¢ и u²ÎV, которое оно соединяет. При этом u¢ (или u²) и ребро ℓ называется инцидентными друг другу, а вершины u¢ и u², являющиеся для ребра ℓ концевыми точками, называются смежными (вместе uÎV и ℓÎE можно записать uÎG и ℓÎG).
Ребро, соединяющее две вершины, может иметь направление
- оно называется направленным или ориентированным (или дугой). Обозначение: граф содержащий направленные дуги – ориентированным (или орграфом), а ненаправленные – неориентированным (н-графом).
Ребра инцидентные одной и той же паре вершин, называются параллельными или кратными, а граф – мультиграф. Ребро инциндентное одной вершине – петля. Граф называется конечным, если множество его элементов (вершин и ребер) конечно, граф называется пустым если множество его вершин и ребер пустое. Граф называется псевдографом если
он содержит петли и кратные ребра, без петель и кратных ребер – полным, если каждая пара вершин соединена ребром. Дополнением графа G называется , имеющий те же вершины, и содержащий только те ребра, которые нужно добавить к G чтобы получить полный граф.
Каждому неориентированному графу канонически соответствует ориентированный граф, соединяющий тоже множество вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентным тем же вершинам и имеющим противоположные направления.
Локальной степенью вершины uÎV н-графа G называется количество ребер r(n) инцидентных вершине n. В н-графе сумма степеней всех вершин равна удвоенному числу ребер m графа, т.е. четное (дает вклад 2 в степень вершины deg u): (лемма о рукопожатиях, отсюда следует, что в н-графе число вершин нечетной степенью четно).
Рисунок 7. Виды ребер графа.
Для вершин орграфа определяются две локальных степени:
r1(n) – число ребер с началом в n (выходом)
r2(n) – количество входящих (петля дает вклад 1 в обе степени)
∑r1(n) = ∑r2(n) = m.
Графы G1 и G2 равны, т.е. G1 = G2, если их множества вершин и ребер (выраженных через пары инцидентных им вершин) совпадают: V1 = V2 и Е1 = Е2.
Рисунок 8. Пример равных графов.
Граф считается полностью заданным в строгом смысле, если нумерация его вершин и ребер зафиксирована. Графы, отличающиеся лишь нумерацией вершин и ребер, называются изоморфными.
Рисунок 9. Изоморфные графы.
Пример 1. Задать граф G1, через множество вершин V, и ребер Е, ∆G может быть полностью определен:
- двумя множествами поименованных - V1 = {υ1, υ2,…, υn} и Е1 = {ℓ1, ℓ2, ℓ3, ℓ4} в строгом смысле требуется установление индицированности;
- множеством ребер, каждое из которых представлено парой своих концевых вершин: Е1 ={(υ1, υ4), (υ4, υ3), (υ3, υ5), (υ5, υ2)}.
Порядок указания вершин не важен, G1 н-граф.
Пример 2. Определить типы и взаимоотношения графов, изображенных на рисунке 10.
, имеющий те же вершины, и содержащий только те ребра, которые нужно добавить к G чтобы получить полный граф.
(лемма о рукопожатиях, отсюда следует, что в н-графе число вершин нечетной степенью четно).
G3 – все вершины изолированы G4 и G5 – дополняют друг к другу,