1-База: различия между версиями

'''1-База''' (''[[1-Base]]'') — такой минимальный набор <math>S</math> попарно несмежных вершин, что любая [[вершина]] [[орграф|орграфа]] или принадлежит <math>S</math>, или [[смежные вершины|смежна с некоторой вершиной]] множества <math>S</math>. Каждый орграф имеет [[вершинная база|вершинную базу]], но не каждый имеет 1-базу; однако каждый [[бесконтурный орграф]] имеет 1-базу.

* Харари Ф. Теория графов. —  М.: Мир, 1973.