§ 28. Порядковая функция графа без контуров

Рассмотрим граф без контуров и определим подмножества

где такое наименьшее целое число, что

Легко показать, что подмножества образуют разбиение и вполне упорядочены отношением

Функция определенная равенством

называется порядковой функцией графа без контиров

Рис. 110.

Другими словами, предлагается разбить множество вершин графа без контуров на непересекающиеся подмножества, упорядоченные так, что если вершина принадлежит подмножеству с номером то следующая за ней вершина входит в подмножество с номером, большим

Подмножества этого разбиения называются уровнями.

Пример. На рис. 111 показаны уровни, на которые разлагается множество вершин графа на рис. 110. Каждой вершине этого графа соответствует некоторое , т. е. некоторое Эта порядковая функция задается таблицей

Порядковую функцию графа без контуров можно определить различными способами, в качестве начального множества можно взять произвольное множество вершин, содержащее Порядковая функция позволяет перенумеровать вершины так, что вершины уровня имеют номера меньшие, чем вершины уровня (рис 112). Порядковая функция играет важную роль во многих комбинаторных задачах.

(кликните для просмотра скана)

Понятие порядковой функции для графов с контурами. Порядковая функция классов графа. Рассмотрим классы графа (максимальные сильно связные подмножества)

Рис. 114. (см. скан)

Как мы видели впредыдущем параграфе, эти классы упорядочены и граф классов не имеет контуров, и поэтому можно определить уровни. Например, на рис. 113 показаны уровни для графа классов на рис 96.

Способ нахождения уровней графа без контуров. Для графа на рис. 110 выпишем его булеву матрицу (рис. 114). Образуем строку выписывая для каждой вершины количество предшествующих ей вершин. В качестве уровня берем (им не предшествует никакая вершина). Затем выписываем строку на местах ставим X, а на остальных — количество вершин, предшествующих данной, исключая Вершины, которым соответствуют нули в строке составляют уровень Далее выписываем тем же способом и соответствующие уровни до тех пор, пока это возможно. Тем самым вершины графа распределяются по уровням, как на рис. 111.

Если граф содержит контур, то обязательно появится строка без нулей. Отсюда следует, что описанный способ дает возможность установить наличие контуров в графе.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)