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