Def. Если J есть независимое подмножество в гиперграфе, то порожденный подгиперграф является пустым

H’ = ‹V’,Æ ›

Def. Если J’Ì J, то J’ – независимое подмножество Нподмножество В(Н)\J называется зависимым подмножеством гиперграфа.

Замечание. Минимальное число независимых подмножеств может рассматриваться как минимальное число объектов.

Def. Подмножество ребер является независимым подмножеством гиперграфа таким, что никакие два ребра из этого подмножества не инцидентны одной вершине, называется паросочетанием гиперграфа.

Пример:

Пусть имеются два множества: юношей и девушек и пусть картеж ‹x, y› Î U, xÎ V_ю, yÎ V_д означает, что девушка знакома с юношей, тогда каждое паросочетание соответствует возможному множеству супружеских пар, в котором каждая пара состоит из юноши и девушки, знакомых между собой. Каждый из них участвует не более, чем в одной паре.

Def. Циклом матроида называется минимально зависимое множество такое, что множество С\{l} является независимым для произвольного lÎ С.

Примеры:

3. Пустой гиперграф есть дискретный (простой) матроид.

4. Тривиальный матроид ‹V,{0} › - матроид, независимым подмножеством (базой) которого является пустое множество.

Жадный алгоритм - алгоритм решения комбинаторных задач, в котором на каждом шаге возможные в перспективе преимущества приносятся в жертву для достижения цели. С помощью жадного алгоритма можно найти независимые подмножества с произвольным весом.

Примеры:

1)Пусть задана матрица

7 5 1

А= 3 4 3

2 3 1

Найти подмножество, состоящее из 3-х элементов, такое, что:

§ в каждом столбце не более одного выделенного элемента

§ сумма выбранных элементов является наибольшей

Решение

Упорядочим матрицу

15= J_max3Î B(V)

e₁ = 7V₁ + 3V₂+ 2V₃

e₂ = 3V₁ + 4V₂+ 3V₃

e₃ = 2V₁ + 3V₂+ 1V₃

Очевидно, что столбцы данной матрицы можно трактовать как векторы 3-х-мерного пространства, причем подмножество векторов линейно независимо тогда и только тогда, когда соответствующее множество столбцов линейно независимо. e= V₁ +V₂+V₃

Каждая такая матрица порядка min определяет матроид (M(H)= ‹V, J›), где V- множество всех столбцов, J- множество линейно независимых столбцов.

Имеем матрицу:

7 5 1

А= 3 4 3

2 3 1

2) В данной матрице найти подмножество, состоящее из 3-х элементов, такое, что:

§ выделенный элемент единственный в строке и столбце

§ сумма выбранных элементов является наибольшей

7 5 1

А= 3 4 3

2 3 1

3) Даны конечное множество вершин, семейства его подмножеств и функция веса.

| V| = n; JÍ B(V); w: V® R⁺

Найти подмножество SÍ J с наибольшей суммой max å w (l), lÎ S

Пояснения:

Задачи 1 и 2 являются частным случаем 3: в обоих случаях множество U является множеством позиций матрицы А, а вес (w) ставится в соответствие позиции в матрице-

‹ i, j›.

При этом для первой задачи факт, что S является элементарным независимым подмножеством, означает, что каждый столбец содержит не более одной позиции множества S.

Так как ‹V, J› должен быть матроидом, то жадный алгоритм имеет следующий вид:

1-й шаг: найти такой элемент v_1Î V, что w (e₁)= max w (e)

^{eÎ J}

k-й шаг: найти такой элемент v_kÎ V, что w (e_k)= max w (e)

e₁, e_2…e_kÎ J

Если такого элемента нет, то это означает конец алгоритма.

4)Задача для самостоятельного решения:

Найти такое дерево, в котором вес ребер будет максимален.

Def. Матроид- гиперграф, определяемый заданием множества вершин и семейством независимых подмножеств, аксиомами для которых являются:

§ пустое множество независимо

§ каждое подмножество независимого множества независимо

§ для каждого подмножества независимого множества, содержащегося в К и являющегося максимальным относительно К, имеют единственное (одинаковое) число элементов.

Примеры:

1)Множество строк матрицы (n, m) и семейство всех подмножеств множества V, составленных из ее линейно независимых строк образуют матроид.

2)Множество ребер простого графа и семейство множеств ребер суграфа (остовых? деревьев) образуют матроид.

M= ‹| V| = 5, J› -матроид

Напоминание:

12. Пустой гиперграф (H=‹V, Æ ›) есть свободный матроид (без цикла).

13. Тривиальный матроид (H=‹V, {0}›) есть гиперграф с множеством вершин и одноэлементными подмножествами вершин(в данном случае единственной базой является пустое множество).

Дата добавления: 2014-01-06