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

ОПРЕДЕЛЕНИЕ ГРАФА.

ТЕМА 1.

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

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

графа называется мощностью множества X графа и обозначается |X|=n.

Множество линий, соединяющие любые пары вершин

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

U={u₁, u₂,..,u_m}, где u_i - ребро (дуга) графа.

Суммарное число m всех рёбер графа называется мощностью множества рёбер графа и обозначается |U|=m.

Таким образом, графом можно считать математический объект, который обозначается 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=(u_l,x_k) - это различные дуги в графе G;

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

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

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

Рёбра, подходящие к вершине х, называются инцидентными данной вершине. Соответственно говорят, что вершина х инцидентна рёбрам, подходящим к ней.

Количество рёбер, инцидентных вершине х, называется степенью вершины s(x).

Вершина х называются изолированной, если её степень s(x)

равна нулю.

Граф является конечным, если он имеет конечное число вершин и рёбер.

Бесконечные графы обладают следующими характеристиками:

Вершинами графа служат натуральные числа, причём вершины p и q соединены звеном в том и только том случае, если оба числа p и q простые и | p-q | £ 2. Множество вершин этого графа счётно, а является ли множество рёбер счётным или только конечным – неизвестно до сих пор (проблема близнецов в теории чисел).

Вершинами являются числа 1,2,...,n, а каждое действительное число x, удовлетворяющее условию i < x < i+1, служит дугой из вершины i в вершину i+1. Граф содержит конечное множество вершин и континуум рёбер (дуг).

Вершинами служат все действительные числа, и при фиксифованном d > 0 вершины x и y соединены ребром (звеном или петлёй) тогда и только тогда, когда | x-y | < d. Каждому значению d отвечает свой граф, у которого множества вершин и рёбер оба континуальны.

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