Вершинная база

Cтраница 1

Вершинная база орграфа 0 ( V, Е) - это минимальное подмножество B V, такое, что в каждую вершину V существует путь длины нуль или больше из некоторой вершины, принадлежащей В. [1]

Пример орграфа. [2]

Каждый орграф имеет вершинную базу, но не каждый имеет 1-базу. Например, ни один из контуров нечетной длины не имеет 1-базы. Критерий существования 1-базы у произвольного орграфа еще не найден. В теореме Ричардсона [1] обобщается следствие 16.7 ( а), полученное фон Нейманом и Моргенштерном [1] при исследовании ими теории игр. [3]

Пример орграфа. [4]

Теорема 16.6. Каждый бесконтурный орграф имеет единственную вершинную базу, состоящую из всех вершин с нулевыми полустепенями захода. [5]

Пример орграфа. [6]

Минимальный набор вершин, из которого достижимы все вершины орграфа D, называется вершинной базой орграфа. D достижима из некоторой вершины множества 5 и ни одна из вершин множества S не достижима из любой другой вершины этого множества. [7]

Страницы: 1