Теория независимости в комбинаторике
«Теория независимости в комбинаторике: вводный курс с приложениями к графам и трансверсалям» — это учебник математики для бакалавров по теории матроидов . Он был написан Виктором Брайантом и Хейзел Перфект и опубликован в 1980 году издательством Chapman & Hall.
Темы
[ редактировать ]Основной темой теории независимости в комбинаторике является объединяющая природа абстракции и, в частности, то, как теория матроидов может объединить концепцию независимости, исходящую из разных областей математики. [1] В ней пять глав, первая из которых содержит основные определения теории графов , комбинаторики и линейной алгебры , а вторая из которых определяет и знакомит с матроидами , называемыми в этой книге «пространствами независимости». [2] Как следует из названия, они определяются в основном через свои независимые множества, но эквивалентности с определениями с использованием схем, ранга матроида и функции субмодулярного множества , а также суммы, миноры, усечения и двойники матроидов. также представлены [3]
Третья глава посвящена графическим матроидам , матроидам остовных деревьев в графах. [2] и жадный алгоритм для минимальных остовных деревьев . [3] Четвертая глава включает материал о трансверсальных матроидах , которые можно описать в терминах паросочетаний двудольных графов , а также дополнительные материалы по теории паросочетаний и смежным темам, включая теорему Холла о браке , теорему Менгера (эквивалентность между минимальными разрезами и максимальными множествами, непересекающиеся пути в графах). ), латинские квадраты и гаммоиды . [2] [3] Последняя глава посвящена представлениям матроидов, использующим линейную независимость в векторных пространствах . [2] помечен как приложение и представлен с меньшим количеством доказательств. [1] [3] [4]
Включено множество упражнений различной сложности с подсказками и решениями. [1] [2] [3]
Аудитория и прием
[ редактировать ]Уровень текста соответствует курсам для студентов старших курсов или магистров, [1] с обязательным условием только базовой линейной алгебры, [2] [4] [5] и раскрывает свой материал на более доступном и общем уровне, чем другие тексты по теории матроидов. [3] [4] [6] не согласен с решением книги опустить связанную с ней тему геометрических решеток , Хотя рецензент Доминик Уэлш он называет ее «идеальным учебником для бакалавриата по комбинаторной теории». [2] Майкл Дж. Гэнли также называет это «очень хорошим введением в довольно сложный предмет». [4]
Однако рецензент В. Дёрфлер жалуется, что в книге недостаточно освещено практическое применение и отсутствует надлежащая библиография. [3] Другая жалоба Бернхарда Корте заключается в том, что название книги вводит в заблуждение: «пространства независимости» часто относятся в более общем смысле к абстрактным симплициальным комплексам , в то время как книга гораздо более конкретно концентрируется на матроидах. Корте также повторяет жалобы других рецензентов на недостаточное освещение приложений комбинаторной оптимизации и связей с теорией решеток. [5]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д Ллойд, Э. Кейт (1982), «Обзор теории независимости в комбинаторике », Mathematical Reviews , MR 0604173
- ^ Перейти обратно: а б с д и ж г Уэлш, DJA (октябрь 1981 г.), «Обзор теории независимости в комбинаторике », The Mathematical Gazette , 65 (433): 228, doi : 10.2307/3617158 , JSTOR 3617158
- ^ Перейти обратно: а б с д и ж г Дёрфлер В., «Обзор теории независимости в комбинаторике », zbMATH , Zbl 0435.05017.
- ^ Перейти обратно: а б с д Гэнли, Майкл Дж. (октябрь 1982 г.), «Обзор теории независимости в комбинаторике », Труды Эдинбургского математического общества , 25 (3): 282, doi : 10.1017/s0013091500016795
- ^ Перейти обратно: а б Корте, Бернхард (январь 1982 г.), «Обзор теории независимости в комбинаторике », European Journal of Operational Research , 9 (1): 100–101, doi : 10.1016/0377-2217(82)90025-x
- ^ Радо, Ричард (май 1981 г.), «Обзор теории независимости в комбинаторике », Бюллетень Лондонского математического общества , 13 (3), Wiley: 252–253, doi : 10.1112/blms/13.3.252