База графа

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение[править | править код]

Базой графа является подмножество вершин графа , которое удовлетворяет следующим условиям:

  1. Каждая вершина графа достижима хотя бы из одной вершины множества .
  2. В нет вершины, которая достижима из другой вершины множества .

Свойства[править | править код]

  • В множестве нет двух вершин, которые принадлежат одной и той же компоненте сильной связности графа .
  • В любом графе без циклов существует единственная база. Она состоит из всех таких вершин графа, полустепени захода которых равны 0.

Пример[править | править код]

Базой графа , заданного таблицей дуг, будет являться множество .

0 0 0 1 1
0 0 1 0 0
0 0 0 1 0
0 0 0 0 0
0 0 1 1 0