Ядро реберное: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Ядро реберное''' (''Edge kernel'') - подграф, порожденный объединением таких незав...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Ядро реберное''' (''Edge kernel'') -
'''Ядро реберное''' (''[[Edge kernel]]'') — [[подграф]], порожденный объединением таких независимых множеств [[ребро|ребер]], мощность которых равна ''[[число вершинного покрытия|числу вершинного покрытия]]'' [[граф|графа]]; в общем случае граф необязательно имеет '''ядро реберное''', однако всякий [[двудольный граф]] такое ядро имеет.
подграф, порожденный объединением таких независимых множеств ребер,
мощность которых равна ''числу вершинного покрытия'' графа; в общем случае
граф необязательно имеет '''Я.р.''', однако всякий двудольный граф такое
ядро имеет.
==Литература==
==Литература==
[Харари]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Текущая версия от 12:07, 13 октября 2011

Ядро реберное (Edge kernel) — подграф, порожденный объединением таких независимых множеств ребер, мощность которых равна числу вершинного покрытия графа; в общем случае граф необязательно имеет ядро реберное, однако всякий двудольный граф такое ядро имеет.

Литература

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