[МУЗЫКА] [МУЗЫКА] Добрый день, дорогие слушатели. Мы начинаем сегодня курс «Алгебраическая теория графов». И первый модуль этого курса включает основные понятия, определения, термины, а также мы покажем исторический экскурс, историческое развитие этой математической дисциплины, в основу которой легли линейная алгебра, теория групп и теория графов. Сам термин «алгебраическая теория графов» был введен Норманом Бигсом, когда в 1974 году он опубликовал свою книгу Algebraic Graph Theory. В ней были заложены основы этой новой дисциплины. Книга состояла из трех частей: «Линейная алгебра в теории графов», «Проблемы раскрасок», а также «Симметрия и регулярность». Первая часть книги была посвящена использованию алгебраических методов для решения задач в теории графов, в том числе изучению спектров графов. Во второй части исследовались алгебраические инварианты, а именно свойства этих инвариантов, такие как полиномы хроматические, инварианты узлов и так далее. Такие инварианты графов позволяют изучать структуру графа с использованием алгебраических методов. И наконец, третья, последняя, часть этой книги посвящена исследованию симметрии графов, а также их регулярности. Нужно сказать, что в наши дни алгебраическая теория графов превратилась в абсолютно самостоятельную и очень разветвленную область математики, которая включает в себя в том числе спектральную теорию графов, теорию графов Кэли, а также алгебраическую комбинаторику. Как уже было сказано ранее, алгебраическая теория графов опирается на три основных кита: это теория графов, теория групп и линейная алгебра. Давайте сейчас посмотрим, как исторически развивались эти три дисциплины, эти три теории, а также посмотрим, как получилось, что появилась новая дисциплина — алгебраическая теория графов. Итак, мы знаем все прекрасно, что линейная алгебра является одной из самых старейших математических дисциплин. Существенному развитию линейной алгебры послужило ее использование для решения уравнений с помощью матричных представлений. Огромный вклад в ее развитие внесли Ферма, Эйлер, Лейбниц, Якоби. И этот список можно продолжать. Но давайте мы с вами поговорим о вкладе Леонарда Эйлера. Величайший ученый, просветитель науки, человек, который прожил большую часть своей жизни в России, он развивал не только линейную алгебру. Он также развивал многие области математики, такие как геометрия, теория чисел, математический анализ, комбинаторика. Он также внес свой большой вклад в развитие таких областей, как механика, физика, астрономия — и это неполный список. Но нас в рамках этого курса будет интересовать одна его работа 1736 года. Это работа, в которой он предложил решение знаменитой задачи о Кенигсбергских мостах. Эта задача была поставлена перед Эйлером купцами города Кенигсберга, которые развозили свои товары по всему городу, и в том числе по семи мостам, которые соединяли два острова и берега города. Так вот, на самом деле купцы очень хотели бы проехать по этим мостам ровно один раз — они хотели оптимизировать задачу и вернуться назад. Но у них никак это не выходило. Эйлер взялся за решение этой, в наши дни сказали бы «прикладной задачи», с присущим ему научным подходом. Он сформулировал задачу, он ее формализовал, он решил ее в самом общем виде и заложил основы новой теории, которая сейчас называется теория графов. В своей работе 1736 года, которая, кстати говоря, была написана на латыни, потому что математику в те времена писали именно так — на латыни, так вот, в этой статье не содержалось ни одного символа, ни одного термина, ни одной формулы, которые нам привычны, и ни одного понятия. Но при этом он ввел основные понятия, которые сейчас используются в теории графов, а именно: граф, вершина, ребро. И вот эти понятия уже в следующей лекции будут аккуратно нами введены. А теперь давайте мы вернемся к другой составляющей, важной составляющей алгебраической теории графов, а именно к теории групп. Считается, что первое упоминание о группах, а именно о конечных группах подстановок, появилось в работе Лагранжа 1767 года, эта работа называется «О решении числовых уравнений». Исследованиями в этой же области занимался также Коши, который в 1815 году использовал представление группы через подстановки для решения теперь уже на самом деле классических задач механики. Создатель теории Галуа, Эварист Галуа, был первым, кто в 1832 году использовал термин «группа» для того, чтобы описать множество перестановок, которые замкнуты относительно композиции, а также содержат единичный элемент. В дальнейшем теория групп развивалась благодаря работам Жордана, Бертрана, Кэли, и вот последнему мы особенно благодарны за то, что он ввел новое понятие, а именно понятие графа на группе, то есть он объединил те две теории, которые к этому моменту уже успешно развивались. Артур Кэли, английский математик, ввел это понятие в 1878 году для более наглядного представления структуры группы через порождающее множество. В последние годы теория графов Кэли развивается как отдельная самостоятельная дисциплина алгебраической теории графов. Мы будем более подробно говорить о ней в третьем модуле нашего курса. Там же, в этом же модуле, мы также будем говорить о действии группы на графов и о симметричных графах, исследованиями которых начали заниматься с середины прошлого века, а именно с того момента, когда Робертом Фрухтом было показано существование графа, который является регулярным, но при этом он не имеет никаких симметрий. Это было удивительно в те времена. В настоящее же время эта область охватывает такие дискретные объекты, как дистанционно-транзитивные графы и схемы отношений. Вот о последних мы будем говорить в последнем модуле нашего курса. А дистанционно-транзитивные графы станут объектом исследований того же третьего модуля нашего курса. На этом мы с вами завершаем небольшой экскурс в развитие алгебраической теории графов, из которого вам должна быть более понятна структура нашего курса. В следующий раз мы с вами поговорим об основных понятиях теории графов.
