Графы и сети. Харитонова Е.В. - 11 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

10
● Двудольный граф называется полным двудольным графом K
m,n
, если A
содержит m вершин, B содержит n вершин и для каждого a
∈
A, b
∈
B имеем {a,
b}
∈
E.
Таким образом, для каждого a
∈
A и b
∈
B имеется связывающее их реб-
ро.
Пример. Графы K
1, 2
, K
2, 3
, K
2, 2
, K
3, 3
приведены по порядку на рис. 1.14.
Рис. 1.14.
1.2 Ориентированные графы
Во многих случаях необходимы графы, у которых ребра, по существу,
представляют собой улицу с односторонним движением. Это означает, что если
рассматривается ребро, выходящее из вершины a в вершину b, то нельзя рас-
сматривать выходящим из вершины b в вершину a.
● Ориентированный граф или орграф G, который обозначается
через
G(V, E), состоит из множества V вершин и множества E упорядоченных пар
элементов из V, называемого множеством ориентированных ребер или просто
ребер.
● Элемент множества E называется ориентированным ребром.
● Если (a, b)
∈
E, то a называется начальной вершиной ребра (a, b), а b на-
зывается конечной вершиной.
Понятие ориентированного графа допускает наличие петель, чего не было
в случае простых графов.
Ребро (a, b) ориентированного графа обозначается на диаграмме стрелкой
из a в b.
Отметим, что в простом графе ребро представляется двухэлементным
подмножеством, чтобы
подчеркнуть, что отношение симметрично, в то время
как в ориентированном графе ребро представлено упорядоченной парой, чтобы
акцентировать важность порядка и то, что (a, b) может быть ребром в орграфе,
а (b, a) – нет.
Пример. Орграф, у которого V = {a, b, c} и E = {(a, b), (b, c), (c, b), (c, a)} изображен
на рис. 1.15

Страницы