1.7 KiB
1.7 KiB
Ациклический орграф. Теорема о монотонной нумерации.
Ациклический орграф
- Ациклический орграф - орграф без ориентированных циклов
- Монотонная нумерация вершин графа - нумерация, при котором номер начальной вершины каждого ребра меньше номера конечной вершины
- Полустепень исхода (
deg^-(x)) - число рёбер орграфа, выходящих из вершины x - Полустепень захода (
deg^+(x)) - число рёбер, входящих в вершину x ^3dbfa3
Теорема о монотонной нумерации
Теорема
Для любого ациклического орграфа существует монотонная нумерация его вершин
Доказательство
Присваиваются номера вершинам в порядке возрастания, 1, \dots, k, таким образом уже частичная нумерация монотонна
Выбирается какой-то ориентированный путь P наибольшей длины, проходящий только через вершины, ещё не имеющие номеров. Начальная вершина - \alpha
Пусть \exists вершина b так, что (b,a) \in E , тогда вершина
- не принадлежит P, иначе цикл
- имеет номер, иначе есть путь больше P