База графа

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

Определение

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

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

Свойства

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

Пример

Базой графа $G$, заданного таблицей дуг, будет являться множество $\{x_{1},x_{2}\}$.

	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
$x_{1}$	0	0	0	1	1
$x_{2}$	0	0	1	0	0
$x_{3}$	0	0	0	1	0
$x_{4}$	0	0	0	0	0
$x_{5}$	0	0	1	1	0

Примечания

Одним из источников этой статьи является статья в википроекте «Рувики» («Багопедия», «ruwiki.ru») под названием «База графа», находящаяся по адресу: «https://ru.ruwiki.ru/wiki/База_графа» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?»