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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

10
соединяющие вершину саму с собой. Псевдограф – это пара (V, Е), где V –
непустое множество (вершин), а Е – некоторое семейство неупорядоченных пар
вершин (ребер), не обязательно различных. На рис. 12 приведены мультиграф
(слева) и псевдограф (справа), в основе которых лежит один и тот же граф –
треугольник.
Рис. 12
Часто связи между объектами характеризуются вполне определенной
ориентацией. Например, на некоторых улицах допускается только одностороннее
автомобильное движение, в соединительных проводах электрической цепи задаются
положительные направления токов, отношения между людьми могут определяться
подчиненностью или старшинством. Ориентированные связи характеризуют
переход системы из одного состояния в другое, различные отношения между
числами (неравенство,
делимость). Для указания направления связи между
вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное
таким образом ребро называют
дугой, а граф с ориентированными ребрами –
ориентированным графом (орграфом). Итак, ориентированный граф – это пара
(V, А), где V – множество вершин, А – множество ориентированных ребер (дуг),
А
⊆ V
2
(V
2
– декартов квадрат, состоящий из упорядоченных пар элементов
множества V). Если а=(v
1
, v
2
) – дуга, то вершины v
1
ее начало, а v
2
– конец.
Аналогично определяется
ориентированный мультиграф. Рассматриваются также
смешанные графы, у которых есть и дуги и неориентированные ребра.
Для всех этих видов графов вводится понятие изоморфизма как биекции
между множествами вершин, сохраняющей смежность, кратности ребер, петли и
направления дуг.
Направленный граф – это орграф, не имеющий симметричных
пар ориентированных ребер, т.е. дуг вида (u, v) и (v, u). На рис. 13 приведены все
орграфы с тремя вершинами и тремя дугами; два последних из них – направленные
графы.
Рис. 13
Взвешенные графы
Рассматривая отображения связей между объектами с помощью графов,
можно пойти на дальнейшее обобщение, приписывая ребрам и дугам некоторые
количественные значения, качественные признаки или характерные свойства,

Страницы