Теория графов оперирует формальными моделями объектов, имеет дело со свойствами самих графов независимо от того, какова природа объектов, описываемых графами. Использование аппарата теории графов для разработки алгоритмов конструкторского и технологического проектирования схем ЭВА приводит к повышению эффективности и качества создаваемых объектов.
Понятие графа опирается на понятие множества. Графом можно назвать объект, состоящий из двух множеств: множества точек и множества линий, которые находятся между собой в некотором отношении. Множество точек графа обозначается Х={x1,x2,..,xn}, |X|=n, и называется множеством вершин. Множество линий, соединяющих любые пары вершин
(xi, xj), принадлежащих множеству Х, называется множеством ребер или дуг и обозначается:
U={u1, u2,..,um}, |U|=m, где |U| - мощность (кардинальное число) множества.
Тогда графом можно считать математический объект, который обозначается G=(X,U) и состоит из множества вершин Х и множества ребер или дуг U, находящихся между собой в некотором отношении.
В общем случае множество U можно представить в виде
,
где: - подмножество неориентированных линий, для которых не существенен порядок соединения вершин. Подмножество называется подмножеством ребер.
Причем каждое ребро uiÎ определяется неупорядоченной парой вершин x, y, которые оно соединяет и записывается: ui=(x, y) или ui=(y, x).
- подмножество ориентированных линий, для которых существенен порядок соединения вершин. Подмножество называется подмножеством дуг. Причем каждая дуга ui Î определяется упорядоченной парой (кортежем длины два) вершин xk , yl, которые ui соединяет и записывается:
ui=(xk , yl ).
Заметим, что ui=(xk , yl) и uj=(yl , xk ) - это различные дуги в графе G;
- подмножество линий, каждая из которых выходит и входит в одну и ту же соответствующую этой линии вершину. Называется подмножеством петель.
Каждая петля ui Î может определяться упорядоченной парой, например вида ui=(xk, xk ).
Граф состоит из вершин, которые изображаются нумерованными кружками (или точками) и рёбер, изображаемыми линиями (со стрелками или без),соединяющих некоторые из этих вершин. Однонаправленное соединение двух вершин называется дугой. Двунаправленные или ненаправленные соединения называются звеньями. Рёбра, соединяющие вершину с ней же называются петлями. Рёбра, связанные с i-той вершиной называются инцидентными данной вершине. Данная вершина является инцидентной по от ношению к этим вершинам. Вершины называются изолированными, если ни одно ребро не соединяет их с другими вершинами. Такие вершины называются голыми, если при них нет даже петель. Граф является конечным, если он имеет конечное число вершин и рёбер.
ОБЫКНОВЕННЫЕ ГРАФЫ.
Особо важную роль играют так называемые обыкновенные графы. Граф этого класса характеризуется следующими четырьмя свойствами:
1) он конечен;
2) он является неориентированным, т. е. не содержит дуг;
3) он не содержит петель;
4) он не содержит "параллельных" ("кратных") рёбер; иначе говоря, никакие две его вершины не могут соединяться более чем одним ребром (звеном).
Определение:
Обыкновенный граф - есть неориентированный униграф без петель. Униграф - это граф, в котором смежные вершины связаны только одним неориентированным ребром.