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

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


examination:diskretka:question20

Вопрос №20. Базисный граф.

Базисный граф: пусть имеется орграф Г; минимальная часть графа Г, индуцирующая на множестве вершин графа Г отношение достижимости графа Г, называется базисным графом графа Г.

Базисный граф графа Г определяется следующими условиями:

  1. Элемент нумерованного спискаесли в Г имеется путь, соединяющий 2 произвольно взятые его вершины, то и в базисном графе графа Г существует путь, содержащий эти вершины (в том же направлении)
  2. Элемент нумерованного спискаминимальность: любая собственная часть базисного графа графа Г базисным графом графа Г не является

Замечание 1: вообще говоря, орграф имеет более 1 базисного графа Замечание 2: если орграф Г конечен, то он всегда имеет хотя бы 1 базисный граф. Доказательство тривиально: следует последовательно уменьшить исходный граф, удаляя его дуги. После удаления очередной дуги надо проверить, индуцирует ли образовавшаяся часть графа Г на вершинах графа Г отношение достижимости. Если индуцирует, то процесс надо продолжить, если нет, то та часть графа Г, которая была получена в процессе осуществления алгоритма непосредственно перед данной частью и является базисным графом.

Замечание: теорема о существовании базисного графа в конечном орграфе может быть распространена на случай произвольного орграфа. Такое обобщение требует применения аксиомы выбора (точнее леммы Цорна).

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