4183
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''1-База''' (''1-Base'') - такой минимальный набор <math>S</math> попарно несмежных верши...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
'''1-База''' (''1-Base'') | '''1-База''' (''[[1-Base]]'') — такой минимальный набор <math>S</math> попарно несмежных вершин, что любая [[вершина]] [[орграф|орграфа]] или принадлежит <math>S</math>, или [[смежные вершины|смежна с некоторой вершиной]] множества <math>S</math>. Каждый орграф имеет [[вершинная база|вершинную базу]], но не каждый имеет 1-базу; однако каждый [[бесконтурный орграф]] имеет 1-базу. | ||
такой минимальный набор <math>S</math> попарно несмежных вершин, что любая | |||
вершина орграфа или принадлежит <math>S</math>, или смежна с некоторой | |||
вершиной множества <math>S</math>. Каждый орграф имеет вершинную базу, но | |||
не каждый имеет 1-базу; однако каждый бесконтурный орграф | |||
имеет 1-базу. | |||
==Литература== | ==Литература== | ||
* Харари Ф. Теория графов. — М.: Мир, 1973. |