Конспект лекций Дискретная математика

Ориентированные графы.

Понятие ориентированного графа (орграфа) было определено ранее. Сейчас рассмотрим подробнее, как выглядят в таком графе пути и циклы.

Пусть дан ориентированный граф . Каждое ребро имеет начало и конец ; также говорят, что данное ребро выходит из вершины и входит в вершину .

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

Определение. Путь из вершин и рёбер – это такая последовательность рёбер и вершин графа , в которой вершина является началом го ребра, а вершина его концом. Вершина называется началом пути , вершина его концом, число рёбер длиной пути.

Путь, состоящий из одной вершины, имеет нулевую длину. Каждому пути ненулевой длины взаимно однозначно соответствует последовательность рёбер этого пути. Её называют путём из рёбер. Такое понятие пути – аналог соответствующего понятия для неориентированного графа. Наконец, для графа, не содержащего кратных рёбер, можно указать взаимнооднозначное соответствие с последовательностью вершин пути. В зависимости от ситуации удобнее использовать тот или иной способ обозначения пути.

Определение. Путь называется ориентированным циклом, если состоит более, чем из одного элемента, и его начало совпадает с его концом.

Начало цикла обычно не фиксируется, иначе говоря, все пути, получающиеся друг из друга циклическими сдвигами – это один и тот же цикл. Определение простого ориентированного цикла аналогично соответствующему определению для неориентированного цикла – это цикл, в котором каждая вершина инцидентна ровно двум его рёбрам. Любой граф, содержащий циклы, можно “укоротить” до простого. Граф, не содержащий циклов, называется ациклическим.

Определение. Вершина ориентированного графа называется начальной, если в неё ни входит ни одно ребро и конечной, если из неё не выходит ни одно ребро.

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

Пусть вершины конечного ориентированного графа пронумерованы от 1 до . Нумерация вершин называется правильной на ребре , если и правильной на графе , если она правильна на всех его рёбрах. Правильная нумерация вершин графа возможна только в том случае, если он ациклический.

Понятия длины путей, протяжённости и расстояния между вершинами определяются для ориентированного графа так же, как для неориентированного графа.

Содержание