Инструменты пользователя

Инструменты сайта


examination:diskretka:question14

Вопрос №14. Ранги вершин ориентированного графа.

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

Замечание: во всяком конечном орграфе, не содержащем циклов, найдется хотя бы 1 начальная и конечная вершины.

Максимальным рангом R(V) вершины V в графе Г называется максимальная длина путей в графе Г, соединяющих какую-либо начальную вершину с вершиной V.

Замечания:

  1. Элемент нумерованного спискакогда V-начальная вершина, R(V)=0
  2. Элемент нумерованного спискаесли через вершину V проходит цикл, то R(V) не определен, в этом случае он равен плюс бесконечности
  3. Элемент нумерованного спискав конечном орграфе, не содержащем циклов, все максимальные ранги конечны

Аналогичным образом определяется минимальный ранг вершины графа. Заметим, что если не существует ни одного пути, соединяющего какую-либо начальную вершину графа Г с вершиной V, то min r(V)= -r(V)

Утверждение: в конечном орграфе Г, не содержащем циклов, R(V)=max(R(V’))+1 по всевозможным дугам графа Г(V’,V). V’-начало, V-конец.

Аналогично для r(V);

examination/diskretka/question14.txt · Последние изменения: 2014/01/15 08:14 (внешнее изменение)