26032001 (1109979), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Доказательство (леммы). От противного. Выберем любую вершину и, исходя из нее, будем двигаться по ребрам в том направлении, какое приписано данному ребру. Если из каждой вершины выходит хотя бы одно ребро, то это будет возможно делать всегда. Вследствие конечности графа в какой-то момент мы должны будем вернуться в точку, в которой уже были. Но это будет ориентированный цикл.

Утверждение. В любом конечном ориетированном графе без ориентированных циклов можно занумеровать вершины первыми натуральными числами так, чтобы каждое ребро было направлено от вершины с меньшим номером в вершину с большим номером.

Добавим также, что если граф бесконечен, то это утверждение будет верно, если вместо натуральных чисел можно использовать целые.

Доказательство. Индукцией по числу вершин. Если граф состоит из одной вершины, то в нем нет ребер (любое ребро было бы ориентированным циклом). Сопоставим этой вершине номер 1. Предположим, что утверждение верно для всех графов с числом вершин, меньшим . Теперь допустим, что имеющийся граф состоит из вершин. По лемме, существует вершина, из которой не выходит ни одного ребра. Сопоставим этой вершине номер и рассмотрим граф, который получается из данного выкидыванием этой вершины и всех ребер, концом которых она является. По предположению, его вершины можно занумеровать числами , так чтобы ребра выходили из вершин с меньшим номером и входили в вершины с большим номером. Вернемся к графу с вершинами и покажем, что при такой нумеровке он удовлетворяет условиям утверждения. Любое ребро, соединяющее вершину с номером с какой-то другой, входит в нее, а потому выходит из вершины с меньшим номером. Любое ребро, концом которого вершина с номером не является, по предположению индукции направлено от вершины с меньшим номеров в вершину с большим номером.

Характеристики

Список файлов лекций