Дискретно-непрерывная математика (стр. 16 )

свойствами

а система циклов матроида М — следующими свойствами:

Можно доказать, что есть множество баз некоторого матроида М*. Матроид М* называют двой­ственным к М. Базу В* и цикл С* матроида М* называют соот­ветственно кобазой и коциклом матроида М. Множество всех ко­циклов М обозначается через так что и

Можно показать: если обладает свойствами и

— свойствами то обладает свой-

ствамит. е. есть матроид. Для Т 2E и ХЕ

назовем систему множеств {А : А Т, A X) ограничением Т|х системы Т на множество X.

Очевидно, М|х есть матроид. Обозначим М|х через М·X или М\, а (М*|х)* через М×Х или М\Х. Очевидно,

Матроид М·X=М\ называют матроидом-ограничением М на X, а М·X=М\ — матроидом-сжатием М на X.

Согласно все базы матроида М имеют одинаковое число элементов, которое называется рангом матроида М и обозна­чается через r(М). Число r*(М)= |Е| — r(М) называется корангом М и, очевидно, есть ранг

Целочисленная функция ρM = ρ на множестве 2Е всех подмно­жеств из Е называется ранговой функцией матроида M, если для ХЕ, так что ρ(X) есть мощность макси­мального независимого множества в X. Вместо ρM* пишем ρ*. Можно доказать, что ранговая функция матроида обладает следующими свойствами:

Функция cl: 2е → 2е называется оператором замыкания для M, если для любого Можно

доказать, что оператор замыкания обладает свойствами

Из свойства циклон следует: если X М, но для х Е \ X

X + х М, то и X + х существует единственный цикл и oн содержит х; обозначим этот цикл через С(М, X + х) или просто С(Х + х). Очевидно, X + х \ у М, если и только если либо X + х М, либо X + х М, по у С(М, X + х).

Цикл (коцикл) матроида М, состоящий из одного элемента, называется петлей М (соответственно копетлей или перешей­ком М). Множество всех копетель матроида М обозначается че­рез I(М). Положим

D(M) = E\I(M). Можно доказать, что D(М) есть множество всех элементов е Е таких, что е при­надлежит некоторому циклу из (M), а именно: Матроид М называется свободным, если D(M)= Ø.

2.2. Для ориентированного графа Г через V Г и ЕГ обознача­ется множество вершин и дуг графа Г соответственно. Путь Р в Г — это последовательность вершин (р0, …, pk) такая, что (pi, pi+1) Е Г для любого i{0, . . ., k — 1}, а k есть длина пу­ти Р. Если в этой последовательности нет одинаковых вершин, то путь Р называется простым. Для Х VГ через Г(Х) обозна­чается множество всех вершин в Г, достижимых по путям из X, так что Х Г(Х). Положим (считаем, что Ø V Г, так что Очевидно, подмножество вершин в Г принадлежит семейству подмпожестн если и только если ни одна дуга графа Г не выходит из X. Мно­жество всех дуг Г, выходящих в X (начало входящей дуги — в VГ \ X, а конец — в Х), образует так называемый ориентиро­ванный разрез орграфа Г. Очевидно, есть решетка мно­жеств, замкнутая относительно объединения. Будем называть решеткой ориентированных разрезов графа Г. Пусть А1, . .., Ап — бикомпоненты графа Г. Тогда (Г(Аі) : i = 1, . .., п) есть множество всех так называемых join-неразложимых элемен­тов решетки а (А1, . .., Ап) — главное разбиение для ре­шетки множеств .

2.3. Пусть есть последовательность систем множеств Ai на Е. Система множеств называется суммой систем

А1, . .., Аk и обозначает­ся через A1 + . . . + Ak или

Последовательность λ=(X1, .. ., Xk) множеств из Е назовем

-последовательностью или -упаковпой, если Xi Ai и при i ≠ j. Если ХА, то существует и, вообще говоря, не одна -последова­тельность такая, что Такую -последовательность назовем -разбиением или -раскраской множества