Дискретная математика

47 § 12. Матроиды Матроидом М=(Е;Х) называется конечное множество Е, \ Е\ = п, я семейство его подмножеств X, X clF, такое, что вьшолняются следующие три аксиомы: Ml: 0еХ\ М2: если А еХи ВсА, то В еХ\ МЗ: если А,В еХ и \ в\= \ А\+\ ,го Зе, е еВ\А, такой, что Аи{е} еХ. Элементы множества X называются независимыми, а осталыше элементы из 2^ - зависимыми множествами. Рассмотрим примеры матроидов. 1. Пусть Е - произвольное конечное множество, &X = 2^. Тогда М=(Е;Х) будет матроидом, ибо, как легко убедиться, выполняются все аксиомы (условия) матроида. Такой матроид называется свободньш матроидом. Положим, что Е={а,Ъ}, тогда 1 ' = {0, {а}, {6}, {а,6}}. Следовательно, М = {{а,Ь}; {0, {я). {Ь}, {а,Ь}}} является свободным матроидом. 2. Пусть Е - множество линейно независимых векторов я X = 2^'. Тогда, как легко видеть, М=(Е;Х) будет матроидом. 3. Пусть имеем граф G = (V,X). Положим Е = X, а Y состоит из ациклических подграфов графа G. Пусть SG обозначает множество всех ациклических подграфов графа G. Можно проверить, что для М =(X;SG} все условия (аксиомы М1-МЗ) выполняются. Следовательно, М= является матроидом. Выясним, каким образом матроиды связаны с алгебрами. Пусть задана функция, аргументы и значения которой принадлежат множеству А. График одноаргументной функции y-fCx) (хеА, уеА) является подмножеством декартового произведения .4x4, т. е,: faAxA. Для двухаргументной функции >'=/(3c;,X2j (xjeA.xieA, уеА) получим, что отношение (функция) / является подмножеством декартового произведения . 4 т . е.: faAxAxA. Очевидно, что для п аргументной функции y=f(x,,X2,..., xj (xieA, ..., х„еА, у еА) имеем: fcAxAx...xA. v , ) Y (п+\) раз Для функции константы/(число аргументов равно нулю), очевидно имеем;