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

Общие понятия

Графы помогают описывать и исследовать различные системы объектов и их связи. Например, в графе, изображенном на рис. 1, точки (вершины графа) можно интерпретировать как города, а линии, соединяющие вершины (ребра), как дороги, соединяющие эти города.

Рис. 1.

Формальное определение графа таково [1-8]. Графом Г=(V, X) называется пара множеств: V – множество, элементы которого называются вершинами, X – множество неупорядоченных пар вершин, называемых ребрами. Если v, w Î V, x=(v,w)ÎX, то говорят, что ребро x соединяет вершины v и w или x инцидентно v и w. Таким образом, {v,w} – обозначение ребра. Если Х представляет собой упорядоченные пары (т. Е. X – подмножество декартова произведения V×V), то граф называется ориентированным, а пары {v,w} называют дугами. Если множеству X принадлежат пары v = w, то такие ребра (v, v) называют петлями. Существование одинаковых пар {v,w} соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер называют количество таких одинаковых пар.

Например, кратность ребра { v ₁,v₂} в графе, изображенном на рис. 2, равна двум, кратность ребра { v ₃,v₄} − трем.

Рис.2.

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

Заметим, что графом также называют мультиграф, в котором ни одна пара не встречается более одного раза.

Итак, используемые далее обозначения:

V – множество вершин;

X – множество ребер или дуг;

v (или v_i)– вершина или номер вершины;

G, G ₀ – неориентированный граф;

D, D ₀ – ориентированный;

{ v, w } − ребра неориентированного графа;

{ v, v } – обозначение петли;

(v, w) − дуги в ориентированном графе;

v, w – вершины, x, y, z – дуги и ребра;

n (G), n (D) количество вершин графа;

m (G) – количество ребер, m (D) – количество дуг.

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