Составители:
Рубрика:
Если V — непустое множество вершин, а E — множество дуг
(ориентированных ребер), то G = (V, E) называется ориентирован-
ным графом (орграфом).
Ориентированный граф порождает (вообще говоря, неодно-
значное) отображение Γ вершин: если (u, v) — дуга, то по опре-
делению v = Γu, а если из вершины u не исходит ни одной дуги, то
полагают Γu = θ. Говорят, что отображение Γ задает отношение
предшествования.
Для ориентированных графов термины ребро, цепь, цикл,
связность обычно заменяются на термины дуга, путь, контур,
сильная связность.
Число дуг, образующих путь, называется длиной пути.
Простой путь (т.е. путь, не имеющий кратных ребер) макси-
мально возможной длины называется критическим путем графа.
Граф называется ациклическим, если он не имеет циклов.
Граф называется помеченным, если его вершины снабжены
некоторыми метками (например, номерами).
Иногда рассматривают частично упорядоченные графы, в ко-
тором лишь часть ребер имеет ориентацию.
Если на каком-либо этапе исследования для ориентированного
графа используется терминология, введенная для неориентирован-
ного графа, то это значит, что ориентация графа не принимается
во внимание.
§ 3. Топологическая сортировка
Вначале будем рассматривать графы без висячих ребер.
Теорема 3.1. В любом ориентированном ациклическом графе
существует хотя бы одна вершина, для которой нет предшеству-
ющей, и хотя бы одна вершина, для которой нет последующей.
Д о к а з а т е л ь с т в о. Если для каждой вершины графа есть
предшествующая, то ввиду конечности числа вершин в рассматри-
ваемом графе есть контур (цикл), а значит, он не ациклический.
Аналогично устанавливается второе утверждение. Теорема доказа-
на.
Дальше вершину графа будем помечать номером т.е. припи-
сывать ей то или иное натуральное число; вершину, помеченную
номером j будем обозначать v
j
.
43
Страницы
- « первая
- ‹ предыдущая
- …
- 40
- 41
- 42
- 43
- 44
- …
- следующая ›
- последняя »
