Монография по современному, бурно развивающемуся разделу дискретной математики — теории перечисления графических объектов. Имя первого автора хорошо известно по переводам его статей и книги «Теория графов» («Мир», 1973).
В предлагаемой работе наряду с классическими результатами Редфилда, Пойа и де Брейна представлены сравнительно новые факты, установленные Робинсоном, Байнеке и авторами. Последняя глава содержит интересный обзор решённых и нерешённых задач перечисления графов. Изложение систематичное и достаточно подробное.
Книга заинтересует математиков, физиков, экономистов и специалистов, работающих в тех областях знания, где используются идеи и методы комбинаторного анализа.
В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными приложениями её в таких науках, как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от неё, — экономику, социологию, лингвистику и др. Давно известны тесные контакты теории графов с топологией, теорией групп и теорией вероятностей. Особо важная взаимосвязь существует между теорией графов и теоретической кибернетикой (особенно теорией автоматов, исследованием операций, теорией кодирования, теорией игр). Широко используется теория графов при решении практических задач на вычислительных машинах.
За последние годы тематика теории графов стала значительно разнообразней, резко увеличилось количество публикаций.
Предлагаемая книга написана одним из видных специалистов по дискретной математике. Несмотря на небольшой объем и конспективный характер изложения, книга достаточно полно освещает современное состояние теории графов. Она, безусловно, будет полезна студентам университетов и технических вузов, и, несомненно, займет известное место в кругу научных работников, занимающихся проблемами дискретной математики.
Пусть ( U = {u_1, u_2, \ldots, u_m, \ldots} ) — исходный алфавит переменных (аргументов) и ( E_2 = {0, 1} ).
ОПРЕДЕЛЕНИЕ. Функция ( f(u_{i_1}, u_{i_2}, \ldots, u_{i_n}) ), где ( u_{i_s} \ne u_{i_t} ) при ( s \ne t ), аргументы и значение которой определены на множестве ( E_2 ), называется функцией алгебры логики или булевой функцией.
ЗАМЕЧАНИЕ. Чтобы избежать сложных обозначений для индексов переменных, мы будем употреблять в качестве произвольных символов алфавита ( U ) символы ( x, y, z, \ldots ), а также эти символы с индексами ( x_1, x_2, \ldots, y_1, y_2, \ldots ).
Об академическом издании сочинений Римана, задачей которого было бы воспроизведение и критическое изучение всего, что сохранилось в его научном наследии или, будучи записано рукой его друзей и учеников, должно было бы рассматриваться как подлинно ему принадлежащее, можно говорить как о памятнике Риману, как о деле высокой важности, для выполнения которого у нас нет, однако, никаких предпосылок.
Не менее значительной и, возможно, актуальной была бы задача — проследить развитие идей Римана от их возникновения вплоть до наших дней: расчленить всё творчество Римана на составные части и, устранив небольшую долю заведомо устаревшего (не скрывающего исторической роли), сделать оставшееся фундаментом обширного построения, в котором были бы отражены, систематизированы и увязаны с их первоисточниками успехи нескольких поколений математиков.
Предпринять такую работу было бы под силу мощному авторскому коллективу, и созданное Риманом — пусть его большая слава — растворилось бы в энциклопедии современной математики.
В последнее время теория графов стала важнейшим математическим инструментом, широко используемым в таких областях науки, как исследование операций, лингвистика, химия, генетика и др. Книга Р. Уилсона является вводным курсом в теорию графов; вместе с тем она затрагивает целый ряд интересных и сложных задач. В ней дано хорошее введение в теорию матроидов, доказаны теоремы о связанности и укладках, приведено много упражнений разной степени трудности.
Книга будет полезна студентам, изучающим дискретную математику. Ее можно рекомендовать и как учебное пособие специалистам в области техники, занимающимся прикладными задачами теории графов.
Книга написана на основе лекций, прочитанных видным французским математиком. С присущим автору мастерством в этих лекциях изложены основы теории когомологий топологических вполне несвязных групп и их многочисленные приложения к теории чисел и алгебраической геометрии, концентрирующиеся вокруг понятий когомологической размерности поля, диофантовых проблем в теории алгебраических групп и задач двойственности.
Книга представляет большой интерес для математиков различных специальностей, начиная со студентов старших курсов.
Книга Дж. Риордана содержит оригинальное изложение комбинаторного анализа — области математики, близкой к теории чисел, алгебре, теории вероятностей и имеющей большое прикладное значение. Основным аппаратом, которым пользуется автор при решении задач комбинаторики, является метод производящих функций и символическое исчисление. В конце каждой главы имеется большое число задач, помогающих активно усваивать изложенные в книге методы.
На русском языке нет книг, посвященных систематическому изложению комбинаторного анализа. Перевод книги Дж. Риордана восполняет этот существенный пробел. Книга, несомненно, будет полезна научным работникам и инженерам различных специальностей, а также студентам и аспирантам, желающим расширить и углубить свои знания в области комбинаторики.
Каково наименьшее число цветов, достаточное для раскраски любой карты, изображенной на сфере, таким образом, чтобы соседние страны были окрашены в разные цвета? Эта знаменитая «проблема четырех красок» еще в конце прошлого века была обобщена на случай карт, расположенных на произвольных поверхностях.
И хотя сама проблема четырех красок более ста лет оставалась нерешенной, задача о раскраске карт для всех ориентируемых поверхностей, отличных от сферы, была недавно решена. Полное решение этой задачи и составляет основу книги Г. Рингеля — известного специалиста в области теории графов, внесшего большой вклад в решение задачи о раскраске карт.
Книга написана доступно и будет полезна широкому кругу читателей, интересующихся современными проблемами математики.
Развитие математики за последние 10–20 лет, в особенности бурный рост вычислительной техники, привел не только к расширению приложений этой науки, но и к перестройке ее содержания. Одной из основных черт этой перестройки является рост роли так называемой конечной математики, в частности, одной из важнейших ее частей — комбинаторных методов.
Комбинаторные идеи и методы всегда были тесно связаны с практическими задачами. Эта связь отчетливо выражена в большинстве книг и статей, посвящаемых комбинаторике. В качестве примера можно указать книгу Риордана „Введение в комбинаторный анализ“ (ИЛ, 1963), а также выпущенный в конце 1964 г. Калифорнийским университетом (США) сборник „Applied combinatorial mathematics“.
Теоретические основы комбинаторной математики, однако, развиты еще недостаточно и сильно отстают от требований практики. Значение предлагаемой вниманию читателей книги Райзера состоит прежде всего в том, что в ней рассматриваются теоретические проблемы комбинаторики. Книгу выгодно отличают обилие исходных теоретических позиций, органическое единство в изложении материала, строгость математических суждений и доказательств.
Журналисты любят писать о физиках с их огромными синхрофазотронами, мощными лазерами, сверхпроводящими материалами. Любят рассказать и об инженерах. Охотно поведают о химиках, создающих новые материалы; о биологах, постигающих тайны жизни. А вот о математиках писать не любят. Нет здесь ничего впечатляющего. Ну, доказал математик десяток-другой теорем, так ведь их не только понять - произнести трудно, язык сломаешь о специальные термины, которыми напичкана эта наука. Вот и остается математика все время как бы в тени. А ведь новых результатов в математике ждут и физики, и химики, и биологи, и инженеры. И не только ждут, а включают математиков в свои исследовательские группы. Потому что математика позволяет с помощью формул записать любые явления, а из этих формул потом можно получить столько информации об объекте исследования, сколько не получишь и из сотни наблюдений. Писать о математике трудно. Каждая ее теорема опирается на другие теоремы, как кирпичи высокой башни, и для того чтобы добраться до верхних рядов, приходится карабкаться по высокой отвесной стене, осваивая достижения предыдущих поколений математиков. Однако о некоторых современных методах математики иногда удается рассказать и неспециалисту, что я и попытался сделать в этой книжке. Небольшие рассказы, из которых составлена книга, можно читать в любом порядке, но в каждой главе первые рассказы попроще, а последние потруднее.
