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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''1-База''' (''1-Base'') - такой минимальный набор <math>S</math> попарно несмежных верши...)
 
Нет описания правки
 
(не показана 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.

Текущая версия от 13:27, 13 ноября 2010

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

Литература

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