АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

В общем случае множество U можно представить в виде

Теория графов оперирует формальными моделями объектов, имеет дело со свойствами самих графов независимо от того, какова природа объектов, описываемых графами. Использование аппарата теории графов для разработки алгоритмов конструкторского и технологического проектирования схем ЭВА приводит к повышению эффективности и качества создаваемых объектов.

Понятие графа опирается на понятие множества. Графом можно назвать объект, состоящий из двух множеств: множества точек и множества линий, которые находятся между собой в некотором отношении. Множество точек графа обозначается Х={x₁,x₂,..,x_n}, |X|=n, и называется множеством вершин. Множество линий, соединяющих любые пары вершин

(x_i, x_j), принадлежащих множеству Х, называется множеством ребер или дуг и обозначается:

U={u₁, u₂,..,u_m}, |U|=m, где |U| - мощность (кардинальное число) множества.

Тогда графом можно считать математический объект, который обозначается G=(X,U) и состоит из множества вершин Х и множества ребер или дуг U, находящихся между собой в некотором отношении.

В общем случае множество U можно представить в виде

,

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

Причем каждое ребро u_iÎ определяется неупорядоченной парой вершин x, y, которые оно соединяет и записывается: u_i=(x, y) или u_i=(y, x).

- подмножество ориентированных линий, для которых существенен порядок соединения вершин. Подмножество называется подмножеством дуг. Причем каждая дуга u_i Î определяется упорядоченной парой (кортежем длины два) вершин x_k , y_l, которые u_i соединяет и записывается:

u_i=(x_k , y_l ).

Заметим, что u_i=(x_k , y_l) и u_j=(y_l , x_k ) - это различные дуги в графе G;

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

Каждая петля u_i Î может определяться упорядоченной парой, например вида u_i=(x_k, x_k ).

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

ОБЫКНОВЕННЫЕ ГРАФЫ.

Особо важную роль играют так называемые обыкновенные графы. Граф этого класса характеризуется следующими четырьмя свойствами:

1) он конечен;

2) он является неориентированным, т. е. не содержит дуг;

3) он не содержит петель;

4) он не содержит "параллельных" ("кратных") рёбер; иначе говоря, никакие две его вершины не могут соединяться более чем одним ребром (звеном).

Определение:

Обыкновенный граф - есть неориентированный униграф без петель. Униграф - это граф, в котором смежные вершины связаны только одним неориентированным ребром.

2. СПОСОБЫ ЗАДАНИЯ ГРАФОВ.

Дата добавления: 2015-09-27 | Просмотры: 476 | Нарушение авторских прав