Jump to content

Теория независимости в комбинаторике

«Теория независимости в комбинаторике: вводный курс с приложениями к графам и трансверсалям» — это учебник математики для бакалавров по теории матроидов . Он был написан Виктором Брайантом и Хейзел Перфект и опубликован в 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]

  1. ^ Перейти обратно: а б с д Ллойд, Э. Кейт (1982), «Обзор теории независимости в комбинаторике », Mathematical Reviews , MR   0604173
  2. ^ Перейти обратно: а б с д и ж г Уэлш, DJA (октябрь 1981 г.), «Обзор теории независимости в комбинаторике », The Mathematical Gazette , 65 (433): 228, doi : 10.2307/3617158 , JSTOR   3617158
  3. ^ Перейти обратно: а б с д и ж г Дёрфлер В., «Обзор теории независимости в комбинаторике », zbMATH , Zbl   0435.05017.
  4. ^ Перейти обратно: а б с д Гэнли, Майкл Дж. (октябрь 1982 г.), «Обзор теории независимости в комбинаторике », Труды Эдинбургского математического общества , 25 (3): 282, doi : 10.1017/s0013091500016795
  5. ^ Перейти обратно: а б Корте, Бернхард (январь 1982 г.), «Обзор теории независимости в комбинаторике », European Journal of Operational Research , 9 (1): 100–101, doi : 10.1016/0377-2217(82)90025-x
  6. ^ Радо, Ричард (май 1981 г.), «Обзор теории независимости в комбинаторике », Бюллетень Лондонского математического общества , 13 (3), Wiley: 252–253, doi : 10.1112/blms/13.3.252
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 872fc4954979fd74e1fdbd9462505b36__1631407620
URL1:https://arc.ask3.ru/arc/aa/87/36/872fc4954979fd74e1fdbd9462505b36.html
Заголовок, (Title) документа по адресу, URL1:
Independence Theory in Combinatorics - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)