4. Базы и антибазы
База В графа есть множество вершин, из которого достижима любая вершина графа и которое является минимальным в том смысле, что не существует собственного подмножества в В, обладающего таким свойством достижимости.
Если мы обозначим через R(В) множество вершин, достижимых из вершин множества В, т.е.
то В является базой тогда и только тогда, когда
R(B) = X и 
ÌB, R(
)?X.
Второе условие ÌВ, R()?X эквивалентно утверждению: хjÏR(xi) для любых двух различных xi, xj Î В, т.е. вершина из В не достижима из любой другой вершины В.
Итак, базой является такое множество B вершин графа G, которое удовлетворяет следующим двум условиям: каждая вершина графа G достижима хотя бы из одной вершины множества B и в B нет вершины, которая достижима из другой вершины множества В. Из этих двух условий получаются следующие утверждения: в множестве В нет двух вершин, которые принадлежат одной и той же СК графа G и в любом графе без циклов существует единственная база; состоящая из всех вершин графа с полустепенями захода равными 0.
Таким образом, в силу этих утверждений база B* конденсации G* графа G состоит из таких вершин графа G*, полустепени захода которых равны нулю. Следовательно, базы графа G можно строить так: из каждой СК графа G, соответствующей вершине базы В* конденсации G* надо взять по одной вершине, т.е. если В* = {S1, S2, ..., Sm}, где т - число вершин-множеств Sj в базе В* графа G*, то базой B является произвольное множество {
}, где 
Î Sj.
Антибаза 
есть множество вершин графа G, таких, что
т.е.
есть такое минимально возможное множество вершин, что какова бы ни была вершина графа G, из нее достижима некоторая вершина в . Свойства антибаз аналогичны свойствам баз, надо только прямые понятия заменить на двойственные. Таким образом, антибаза конденсации G* есть множество вершин в G*, полустепени исхода которых равны 0, и антибазы самого графа G строятся из антибазы графа G* путем выбора по одной вершине в каждой вершине-множестве антибазы * - подобно тому, как это делалось раньше для баз.
Пример
Для графа G, приведенного на рис. 1.3, конденсация G* показана на рис. 1.4. Базой графа G* является множество {х2*, х3*}, поскольку х2* и х3* - единственные вершины в G* с полустепенями захода, равными 0. Базами графа G являются {х5, х6}, {х5, х7} и {х5, х9}.
В примере с графом G, изображенным на рис. 1.3, конденсация G* (рис. 1.4) содержит вершины х1* и х4* с полустепенью исхода, равной 0. Таким образом, антибазой графа G* является множество {х1*, х4*}, а антибазами графа G являются множества {х8, х1}, {х8, х2}, {х8, х3} и {х8, х4}.