Элементы теории графов и их технические приложения - 6 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

6
Рис. 3
преобразований обозначены ребрами, а отношения связей – вершинами. В этом
случае вершинам соответствуют тождественные пары входов и выходов потоков
энергии, массы или информации.
II. Графы и способы их задания.
1. Графы. Различные типы графов.
Многие прикладные задачи сводятся к рассмотрению совокупностей
некоторых объектов, находящихся во взаимной связи и взаимодействии. Например,
при изучении электрических цепей существенным может оказаться характер
соединений различных ее компонентов; органические молекулы образуют
структуры, характерными свойствами которых являются связи между атомами;
различные связи и отношения между людьми, событиями, также могут представлять
интерес
.
В подобных случаях принято, рассматриваемые объекты изображать точками,
называемыми вершинами, а связи между ними – линиями (произвольной
конфигурации), соединяющими их и называемыми ребрами. Графом называют
множество вершин V, связи между которыми определены множеством ребер Е.
Таким образом, граф G, обозначенный как G=(V,Е), представляет собой пару (V, Е),
где V – непустое множество элементов, Е – некоторое подмножество
множества
V
(2)
всех его двухэлементных подмножеств.
Будем рассматривать только конечные графы, т.е. предполагаем множество V
конечным. Множество вершин графа G обозначим символом VG, а множество ребер
графа G – символом ЕG. Вершины и ребра графа называются его элементами. Число
|VG| вершин графа G называется его порядком и обозначается через |G|. Если |G|=n,
|EG|=m, то G называют (n, m) – графом.
Две вершины u и v графа
называются смежными, если множество {u,v}
является ребром; в противном случае вершины называются не смежными. Если
е={u,v} – ребро, то вершины u и v называют его концами, а также, что ребро е
соединяет вершины u и v. Такое ребро обозначается символом uv.
Два ребра называются смежными, если они имеют общий конец. Вершина v и
ребро е называются инцидентными, если v является
концом ребра е ( т.е. е=uv), и
не инцидентными в противном случае.

Страницы