Математическое моделирование на графах. Часть 1. Берцун В.Н. - 38 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

38 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
1.9. Ациклические графы
В орграфе с конечным числом вершин всегда существует хотя бы
один простой путь максимальной длины. Такой путь называется
критическим путем. Это понятие играет важную роль, например,
при анализе сетевых графиков.
Утверждение 1.9. В любом ациклическом орграфе существуют
хотя бы одна вершина с нулевой полустепенью захода и хотя бы од-
на вершина с нулевой полустепенью исхода.
Доказательство. В графе⎯G всегда существует хотя бы один
критический путь. Рассмотрим один из них. Допустим, что первая
его вершина имеет предшествующую вершину. Если предшествую-
щая вершина совпадает с одной из вершин выбранного критического
пути, тогда в графе есть контур. Если предшествующая вершина не
совпадает ни с одной из вершин, образующих критический путь, то-
гда существует путь, имеющий большую длину, чем критический.
Таким образом, в обоих случаях получаем противоречие с предпо-
ложением о том, что полустепень захода первой вершины отлична
от нуля. Аналогичным образом доказывается существование верши-
ны, не имеющей последующей. ■
Утверждение 1.10. Пусть ациклический орграф имеет n вершин.
Существует целое число s ≤ n, для которого все вершины графа
можно так пометить одним из индексов 1,2,…,s, что если дуга из
вершины с индексом i идет в вершину с индексом j, то i < j.
Доказательство. Выберем в графе любое число вершин, кото-
рые не имеют предшествующих, и пометим их индексом 1. Удалим
их из графа вместе с инцидентными им дугами. В оставшемся ацик-
лическом графе выберем любое число вершин, не имеющих предше-
ствующих, и пометим их индексом 2. Снова удалим из графа поме-
ченные вершины и инцидентные им дуги. Так как при каждом шаге
помечается не менее одной вершины, то число различных индексов
не превышает числа вершин графа. ■
Следствия из утверждения 1.10:
1) никакие две вершины с одним и тем же индексом не связаны
дугой;

Страницы