1-База

Материал из WEGA
Версия от 11:53, 29 сентября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''1-База''' (''1-Base'') - такой минимальный набор <math>S</math> попарно несмежных верши...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

Литература

[Харари]