Дискретная математика: графы и автоматы. Альпин Ю.А - 24 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2
Ориентированные графы
§ 1. Взаимодостижимость, компоненты и конденсация
Во многих теоретических и прикладных задачах полезно исполь-
зовать графы, рёбра которых имеют направление. В связи с этим
введём новый тип графов.
Ориентированным графом (орграфом) называется пара (V, E),
где V — непустое множество вершин, E ⊆ V ×V — множество ориен-
тированных рёбер или дуг. Таким образом, дуга — это упорядоченная
пара вершин. Если e = (u, v), то вершина u — начало дуги e, вершина
v — её конец. Говорят, что дуга e выходит из u и входит в v. Гово-
рят также, что e инцидентна вершинам u и v. Дуга (v, v) называется
петлёй. На рисунке дуги графа изображаются стрелками. Иногда в
тексте вместо выражения “дуга ведёт из вершины i в вершину j ” бу-
дем писать i → j. Вершины орграфа смежны, если они соединены
дугой.
Путём длины k в орграфе называют любую последовательность
вершин
v
1
, v
2
, . . . , v
k+1
,
такую, что (v
i
, v
i+1
) — дуга, i = 1, . . . , k. Говорят, что v
1
— начало,
v
k+1
— конец пути. Когда хотят указать начало и конец пути, пишут:
(v
1
, v
k+1
)-путь.
Простой путь — это путь, в котором все вершины различны, кро-
ме, возможно, первой и последней. Если v
1
= v
k+1
, то путь (простой
путь) называется контуром (простым контуром).
Приведём леммы, аналогичные леммам 1 и 2 из §1 гл.1. Их доказа-
тельства в ориентированном случае даже упрощаются. Рекомендуем
доказать их самостоятельно.
Лемма 1. Если существует (u, v)-путь, то существует и про-
стой (u, v)-путь.
Лемма 2. Всякий контур содержит простой контур, причём
каждая вершина и дуга контура принадлежат некоторому просто-
му контуру.
                                Глава 2
                  Ориентированные графы


   § 1. Взаимодостижимость, компоненты и конденсация

    Во многих теоретических и прикладных задачах полезно исполь-
зовать графы, рёбра которых имеют направление. В связи с этим
введём новый тип графов.
    Ориентированным графом (орграфом) называется пара (V, E),
где V — непустое множество вершин, E ⊆ V × V — множество ориен-
тированных рёбер или дуг. Таким образом, дуга — это упорядоченная
пара вершин. Если e = (u, v), то вершина u — начало дуги e, вершина
v — её конец. Говорят, что дуга e выходит из u и входит в v. Гово-
рят также, что e инцидентна вершинам u и v. Дуга (v, v) называется
петлёй. На рисунке дуги графа изображаются стрелками. Иногда в
тексте вместо выражения “дуга ведёт из вершины i в вершину j ” бу-
дем писать i → j. Вершины орграфа смежны, если они соединены
дугой.
    Путём длины k в орграфе называют любую последовательность
вершин
                          v1 , v2 , . . . , vk+1 ,
такую, что (vi , vi+1 ) — дуга, i = 1, . . . , k. Говорят, что v1 — начало,
vk+1 — конец пути. Когда хотят указать начало и конец пути, пишут:
(v1 , vk+1 )-путь.
      Простой путь — это путь, в котором все вершины различны, кро-
ме, возможно, первой и последней. Если v1 = vk+1 , то путь (простой
путь) называется контуром (простым контуром).
      Приведём леммы, аналогичные леммам 1 и 2 из §1 гл.1. Их доказа-
тельства в ориентированном случае даже упрощаются. Рекомендуем
доказать их самостоятельно.
   Лемма 1. Если существует (u, v)-путь, то существует и про-
стой (u, v)-путь.
   Лемма 2. Всякий контур содержит простой контур, причём
каждая вершина и дуга контура принадлежат некоторому просто-
му контуру.

Страницы