Теория графов (фрагменты реферата по истории науки)

[в основном по книгам «Handbook of Graph Theory»¹² и «Graph Theory 1736-1936»²⁷]

Теория, выросшая из игр

Годом зарождения теории графов можно считать 1736-й, когда швейцарский математик Леонард Эйлер опубликовал в Санкт-Петербургской Академии наук работу¹, посвящённую семи мостам города Кёнигсберга (нынешний Калининград). Загадка о том, как пройти по всем мостам ровно однажды, была известна горожанам с тех пор, как все семь мостов были построены, т.е. с XVI века; математик же разработал её формализацию и доказал, что она не имеет решения. Путь, проходящий через все рёбра графа по одному разу, в современной литературе называется эйлеровым путём.

Мостами Кёнигсберга народная изобретательность в области графов не ограничивалась: существовало (и существует по сей день) множество головоломок, в которых требуется начертить какой-либо сложный рисунок одним росчерком пера, что означает нахождение эйлерова пути. Научные работы этой задаче посвятили швейцарский математик Симон Люилье² и французский математик и механик Луи Пуансо³.

Как ни странно, до конца XIX века никто не отметил аналогии задачи о мостах Кёнигсберга с чертёжными головоломками. Впервые это сделал британский математик и юрист Вальтер Уильям Рузе Болл в 1892 году⁴.

С зарождением теории графов связана ещё одна древняя задача — о шахматном коне, который должен пройти через все клетки доски, не побывав на ни на одной дважды. Эта задача, строго говоря, старше шахмат: впервые она упомянута в книге «Китаб Аш-Шатрандж» Абу Бакра Мухаммада ас-Сули, знаменитого игрока в шатрандж, жившего в Арабском (Багдадском) халифате в IX веке. Шатрандж — игра, предшествующая шахматам; ход конём в шатрандже был таким же, как в шахматах. В книге ас-Сули приведены два решения этой задачи (вообще же их триллионы).

Первая публикация⁵, излагающая систематический подход к поиску решений задачи о шахматном коне принадлежала перу Эйлера и увидела свет в 1766 году. Автор привёл в ней способы получения новых решений из уже имеющихся, при этом уделив внимание симметрии пути коня.

Французский скрипач, химик и математик Александр-Теофил Вандермонд в 1771 году продолжил⁶ формализацию Эйлера, освободив её от привязки к шахматной доске как геометрическому объекту, то есть перейдя от количественных характеристик (длин и углов) к качественным (относительному расположению объектов). Этот принцип собственно обозначил отделение теории графов от геометрии и позже лёг в основу другой науки — топологии. Её название было введено немецким математиком Иоганном Листингом в работе⁷ 1847 года, посвящённой эйлеровым путям.

Между задачами о мостах Кёнигсберга и шахматном коне есть принципиальное различие: в первой требуется единожды обойти все рёбра графа, тогда как во второй требуется единожды посетить все вершины. Благодаря этому различию, исследования разных аспектов новой теории долгое время протекали независимо друг от друга.

Вариант второй задачи, заключённый в настольной игре «Икосиан» (Icosian Game), увидел свет в 1857 году по воле сэра Вильяма Гамильтона, ирландского математика, физика и астронома. В основе этой игры лежал процесс поиска замкнутого пути, проходящего через каждую вершину додекаэдра ровно один раз. Автор вывел из своей игры новую алгебраическую структуру⁸, а термин «гамильтонов цикл» стал общепринятым в математике для обозначения замкнутого пути, проходящего через все вершины графа по одному разу.

Независимо от Гамильтона исследования на ту же тему вёл британский математик Томас Киркман. Он обозначил класс многогранников, на которых вышеуказанная задача неразрешима⁹.

Гамильтоновым графам (графам, в которых есть гамильтонов цикл) было посвящено немало исследований и в XX веке^{10 11}. Также с гамильтоновыми графами связана знаменитая «задача коммивояжёра» (travelling salesman problem). Первое упоминание о ней, по косвенным данным, относится к 1831 году. Задача коммивояжёра заключается в том, чтобы обойти все города по одному разу, пройдя минимальное расстояние. Иными словами, это задача поиска минимального гамильтонова цикла. В 1930-х годах она была поставлена и изучена австрийским математиком Карлом Менгером, а позже математиками Принстонского университета Хаслером Уитни и Мериллом Флудом¹². Это одна из так называемых NP-трудных задач¹³. На ней часто производят «обкатку» новых подходов к эвристическому сокращению комбинаторного перебора.

Датой окончательным становления теории графов как самостоятельной математической отрасли можно считать 1936 год, когда венгерский математик Денешем Кёниг написал первую в своём роде монографию "Теория конечных и бесконечных графов«¹⁴.

Деревья

Дерево — связный граф без циклов. Исследования деревьев, в отличие от общей теории графов, с самого начала велись в применении к наукам, а не играм.

Термин (вероятнее всего, позаимствованный из сочетания «фамильное древо») и само понятие ввёл в обращение немецкий физик Густав Кирхгоф. Его публикация 1847 года¹⁵, посвящённая электрическим цепям, внесла огромный вклад в теорию. Автор использовал два правила (ныне известные как «правила Кирхгофа») для составления системы уравнений токов и напряжений в цепи. С целью сокращения количества циклов, участвующих в уравнениях, он предложил концепцию остовного дерева, по которым можно определить набор фундаментальных циклов. В той же работе впервые появляется матрица инциденций — один из ключевых объектов в нынешних компьютерных системах, имеющих дело с графами.

Английский математик Джеймс Сильвестр использовал деревья для описания алгебраических дифференциальных операторов в 1854 году. В его работе¹⁶ появилось определение дерева с выделенным корнем, и соответственно ветвей и листьев такого дерева.

Работа Сильвестра привлекла внимание его друга, математика Артура Кейли, и тот занялся задачей определения количества различных деревьев с выделенным корнем и заданным числом вершин. Свой результат он опубликовал в 1857 году¹⁷. В дальнейшем Кейли делал аналогичные подсчёты для отдельных классов деревьев¹⁸.

В начале 1850-х годов химики разных стран независимо друг от друга определили наличие у химических элементов свойство валентности, благодаря которому образуются химические соединения. Шотландский химик Александр Браун в 1864 году первым предложил¹⁹ использовать «графическую» нотацию для рисования молекул, которая быстро получила распространение и является сегодня общепринятой.

Графическое представление молекул пролило свет на явление изомерии. Изомерами называются вещества разных химических свойств, но одного состава. Стало очевидно, что изомерам соответствуют разные по структуре графы, составленные из одинаковых наборов химических элементов.

Большая часть химических соединений, известных в то время, не содержала циклов, т.е. молекулы являлись деревьями. Кейли, вдохновлённый этим фактом, в 1874 году опубликовал работу²⁰ по перечислению всех изомеров с заданной химической формулой. У молекул нет выделенного корня; перейти на анализ деревьев без корня Кейли помогла публикация²¹ французского математика Камиля Жордана 1869-го года, в которой содержалась формализация изоморфизма и автоморфизма деревьев, а также было введено понятие центра дерева.

У деревьев химических соединений есть ещё одна особенность: их вершины не всегда эквивалентны друг другу, т.к. они имеют метки (atom labels), обозначающие химические элементы. Это обстоятельство породило интерес к перечислению помеченных, а не абстрактных, деревьев. Кейли опубликовал соответствующий результат²² в 1889 году. Тот же результат более аккуратно получил немецкий математик Хейнц Прюфер в 1918 году²³.

Методы перебора изомеров, изложенные Кейли, были неудобны на практике и поэтому не получили признания у химиков. Недостатки методов Кейли были устранены в работе венгерско-швейцарско-американского математика Пойа²⁴ 1935 года.

Сильвестр и другой английский математик, Вильям Клиффорд, в 1878 году предприняли попытку разработать «химико-алгебраическую» теорию, сопоставив атомам алгебраические формы^{25 26}. Теория оказалась несостоятельной, но сама по себе попытка рассматривать графы как независимые объекты «на стыке» двух наук, заслуживает одобрения. Кроме того, в работе Сильвестра впервые появилось слово «граф», прижившееся в научном мире. Сильвестр и Клиффорд, осознав ошибки своей теории, позже пытались ненавязчиво «приписать» её изобретение друг другу²⁷.

Проблема четырёх красок

В 1852 году студент Лондонского Университетского Колледжа Фрэнсис Гутри (Francis Guthrie), составляя карту графств Англии, обнаружил, что для раскраски карты таким образом, чтобы соседние графства имели разные цвета, достаточно четырех красок. Он поделился находкой со своим братом Фредериком (Frederick Guthrie), а тот — с профессором математики Огастесом де Морганом (Augustus de Morgan), от которого о новой гипотезе узнал остальной математический мир. Точную формулировку опубликовал Кейли в 1879 году²⁸.

Гипотеза имела непосредственное отношение к планарным графам — графам, которые можно нарисовать на плоскости так, чтобы рёбра не пересекались. Первое доказательство, опубликованное в том же году лондонским математиком Альфредом Кемпе²⁹, содержало ошибку, найденную в 1890 году британским математиком Перси Хивудом³⁰, который, однако, доказал верность гипотезы для пяти красок.

В течение последующих восьми десятилетий безобидная и не актуальная в картографии проблема четырёх красок была незаменимым «двигателем» математики. В процессе безуспешных поисков доказательства теория графов, алгебра и топология обретали новые интересные результаты.

В начале XX века родились идеи, составившие основу успешного подхода к доказательству гипотезы: немецкий тополог Вернике в 1904 году составил³¹ список т.н. «неизбежных» фрагментов, один из которых присутствует в любой карте. В 1912 году американский математик Дэвид Биркхоф ввёл³² понятие хроматического полинома — числа возможных раскрасок графа заданным количеством цветов, а в 1913 году начал исследование т.н. «сокращаемых» фрагментов карты, обладающих таким свойством, что ни один из них не может появиться в контрпримере к гипотезе о четырёх красках³³. Работа Биркхофа позволила американскому математику Филипу Франклину в 1922 году доказать гипотезу для карт, содержащих не больше 25 стран³⁴.

В 1976 году окончательное доказательство³⁵ было получено профессорами Университета Иллинойса в Урбанэ-Шампейн (UIUC) Вольфгангом Хакеном и Кеннетом Аппелем. Оно всколыхнуло математический мир: впервые для доказательства теоремы использовался компьютер. Более того, только компьютер мог проверить это доказательство: оно состояло из 50 страниц текста и диаграмм, 85 страниц с почти 2500 дополнительными диаграммами, 400 страниц микрофишей, содержащих еще диаграммы, а также тысяч отдельных проверок утверждений, сделанных в 24 леммах основного текста ³⁶.

Доказательство, не поддающееся проверке — нонсенс; опора на вычислительные машины грозит упразднить математику как таковую, переведя её в раздел экспериментальных наук³⁷. На проверку исчерпывающего набора из 1482 сокращаемых фрагментов, перечисленных в доказательстве, ушло 1200 часов машинного времени.

Предпринимались и до сих пор предпринимаются попытки упростить доказательство настолько, чтобы сделать его доступным человеку. В 1994 году четыре американских математика Робертсон, Сандерс, Сеймур и Томас снизили количество число сокращаемых фрагментов до 633³⁸. Их доказательство заслуживает особого внимания тем, что рассматривает задачу, переформулированную в терминах линейной алгебры. Вообще известно более 20 её формулировок, связанных с задачами алгебры, статистической механики и задачами планирования³⁷. В современной теории графов раздел «раскраски» занимает немалую часть и имеет множество приложений в упомянутых областях. Задача определения хроматического числа графа (минимального числа цветов, в которые граф можно раскрасить) и задача «3-раскрашиваемости» планарных графов являются классическими NP-полными задачами¹³.

Прорыв в смысле «человеческого» доказательства был сделан в 2004 году: Джордж Гонтье из исследовательской лаборатории компании Microsoft в Кембридже и Бенджамин Вернер из французского института INRIA перевели программный код доказательства на язык абстрактной логики "Coq«³⁹, и создали интерактивную программу, «помогающую» человеку строить доказательства логических утверждений. Теорема о четырёх красках была таким образом успешно доказана.

Сети и потоки

Сеть — направленный граф с числовыми характеристиками рёбер (дуг), обозначающими пропускную способность. Теория сетей обязана своим возникновением росту промышленности в XX веке и сопутствующей ему проблемы оптимальной доставки грузов по каналам с ограниченной пропускной способностью. Поток в сети соответствует движению грузов по составленным из дуг маршрутам, от определённой точки-источника к точке стока.

Первая работа, касающаяся этой темы, была опубликована в СССР в 1930 году⁴⁰. Наряду с несколькими подходами к решению задачи, в ней было замечено необходимое условие оптимальности потока: остаточный граф потока не должен содержать циклов отрицательной стоимости; однако, обоснования достаточности этого условия приведено не было. Его опубликовал Леонид Канторович в 1942 году⁴¹.

Советская железнодорожная сеть привлекала внимание США в двух аспектах: до Второй мировой войны как пример для подражания, а после, с началом Холодной войны — как стратегический объект потенциального противника, подлежащий уничтожению в случае конфликта⁴². Задача уничтожения транспортного потока в случае войны требует не меньшей эффективности, чем его функционирование в мирное время. Формализация этой задачи содержит понятие разреза — множества дуг между двумя подмножествами исходного множества вершин.

Решения двух задач совпадают: в 1954 году в американской корпорации RAND математики Лестер Форд и Делберт Фалкерсон доказали⁴³, что значение максимального потока в сети равняется значению минимального разреза. Позднее авторы сослались на засекреченную статью⁴⁴ Гарриса и Росса 1955 года, в которой прямо поднимался вопрос эффективного воздушного удара по железнодорожной сети советского блока.

Факт, доказанный Фордом и Фалкерсоном, позволил им разработать эффективный алгоритм поиска максимального потока в сети, который успешно применяется в программах для составления маршрутов доставки грузов, оптимальной транспортировки жидкостей по сетям трубопроводов, а также при анализе автомобильного трафика в городах.

В 1970 году советским учёным Ефимом Диницем был изобретён⁴⁵ более эффективный по времени вариант алгоритма Форда-Фалкерсона. Тот же алгоритм был независимо получен⁴⁶ в 1972 году Джеком Эдмондсом и Ричардом Карпом. Ещё более быстрый алгоритм, получивший название «проталкивания предпотока» (push-relabel) был предложен в 1985 году Голдбергом⁴⁷, и ещё один под названием «поднять-и-в-начало» (relabel-to-front) опубликовали⁴⁸ в 2001 году профессора института MIT Кормен, Лейзерсон и Ривест.

Помимо задачи о максимальном потоке, в теории сетей существуют более сложные, например задача о многопродуктовом потоке, в которой требуется оптимизировать суммарный поток в сети, обладающей рядом пропускных характеристик, заданных в отдельности для каждого продукта. Эта задача в целочисленном варианте является NP-полной⁴⁹.

Литература

[1] Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae. 1736, 8, 128-140.
[2] Simon Antoine Jean Lhuilier. Eléments raisonnés d’algebre. Genève, 1804.
[3] Louis Poinsot. Mémoire sur les polygones et polyedres. J. de l’École Polytechnique. 1810, 9, 16-48.
[4] Walter William Rouse Ball. Mathematical recreations and Problems of Past and Present Times. Macmillan: London, 1892.
[5] Leonhard Euler. Solution d’une question curieuse qui ne paroit soumise a aucune analyse. Mémoires de l’Académie Royale des Sciences et Belles Lettres de Berlin, Anné 1759. 1766, 15, 310-337.
[6] Alexandre-Théophile Vandermonde. Remarques sur des problèmes de situation. Mémoires de l’Académie Royale des Sciences, Paris. 1771, 566-574.
[7] Johann Benedict Listing. Vorstudien zur Topologie. Vandenhoeck und Ruprecht: Göttingen, 1847.
[8] William Rowan Hamilton. Account of the Icosian Calculus. Proceedings of the Royal Irish Academy. 1858, 6, 415-416.
[9] Thomas Penyngton Kirkman. On the Representation of Polyhedra. Proceedings of the Royal Society of London. 1854-1855, 7, 543-544.
[10] Gabriel Andrew Dirac. Some theorems on abstract graphs. Proc. London Math. Soc (3). 1952, 2, 69-81.
[11] Øystein Ore. A Note on Hamiltonian circuits. Amer. Math Monthly. 1960, 67, 55.
[12] Jonathan L. Gross, Jay Yellen. Handbook of Graph Theory. CRC Press, 2004.
[13] Michael R. Garey, David Stifler Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman: San-Francisco, 1979.
[14] Dénes Kőnig. Theorie der endlichen und unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe. Akad. Verlag M.B.H.: Leipzig, 1936.
[15] Gustav Kirchhoff. Über die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 1847, 72, 497-508.
[16] James Joseph Sylvester. On Differential Transformation and the Reversion of Serieses. Proceedings of the Royal Society of London. 1854-1855, 7, 219-223.
[17] Arthur Cayley. On the theory of the analytical forms called trees. Philosophical Magazine (4). 1857, 13, 172-176.
[18] Arthur Cayley. On the analytical forms called trees — Part II. Philosophical Magazine (4). 1859, 18, 374-378.
[19] Alexander Crum Brown. On the theory of isomeric compounds. Transaction of the Royal Society Edinburgh. 1864, 23, 707-719.
[20] Arthur Cayley. On the mathematical theory of isomers. Philosophical Magazine (4). 1874, 47, 444-446.
[21] Camille Jordan. Sur les assemblages des lignes. J. Reine Angew. Math. 1869, 70, 185-190.
[22] Arthur Cayley. A theorem on trees. Quart. J. Math. 1889, 23, 376-378.
[23] Heinz Prüfer. Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 1918, 27, 742-744.
[24] Pólya György. Un problème combinatoire général sur les groupes de permutations et le calcul du nombre des isomères des composés organiques. Comptes Rendus Hebdomadaires des Séances de l’Académie des sciences. 1935, 201, 1167-1169.
[25] James Joseph Sylvester. On an Application of the New Atomic Theory to the Graphical Representation of the Invariants and Covariants of Binary Quantics, With Three Appendices. American Journal of Mathematics, Vol. 1. 1878, 2, 105-125.
[26] William Kingdon Clifford. Notes on Quantics of Alternate Numbers, used as a means for determining the Invariants and Covariants of Quantics in general. Proc. London. Math. Soc. 1878-1879, 10, 124-129.
[27] Edward Keith Lloyd, Norman Biggs, Robin James Wilson. Graph Theory 1736-1936. Oxford University Press, 1986.
[28] Arthur Cayley. On the Colouring of Maps. Proceedings of the Royal Geographical Society and Monthly Record of Geography (1). 1879, 4, 259-261.
[29] Alfred Bray Kempe. On the Geographical Problem of the Four Colours. American Journal of Mathematics. 1879, 2, 193-200.
[30] Percy John Heawood. Map-colour Theorem. Quarterly Journal of Pure and Applied Mathematics. 1890, 24, 332-338.
[31] Paul August Ludwig Wernicke. Über den kartographischen Vierfarbensatz. Math. Ann. 1904, 58, 413-426.
[32] George David Birkhoff. A determinantal formula for the number of ways of coloring a map. Ann. Math. 1912, 14, 42-46.
[33] George David Birkhoff. The Reducibility of Maps. American Journal of Mathematics (35). 1913, 2, 115-128.
[34] Philip Franklin. The four color problem. American Journal of Mathematics. 1922, 44, 115-128.
[35] Kenneth Appel, Wolfgang Haken. Every Planar Map Is Four Colorable. Illinois J. Math. 1977, 21, 429-567.
[36] Kenneth Appel, Wolfgang Haken. The four color proof suffices. The Mathematical Intelligencer 8. 1986, 1, 11.
[37] Алексей Васильевич Самохин. Проблема четырех красок: неоконченная история доказательства. Соросовский образовательный журнал. 2000, 7, 91-96.
[38] Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas. The four colour theorem. J. Combin. Theory Ser. B. 1997, 70, 2-44.
[39] http://coq.inria.fr
[40] А. Н. Толстой. Методы нахождения наименьшего суммового километража при планировании перевозок в пространстве. Планирование перевозок, Транспечать НКПС. 1930, 1, 23-55.
[41] Леонид Витальевич Канторович. О перемещении масс. Доклады Академии Наук СССР. 1942, 37, 227-230.
[42] Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming (91). 2002, 3, 437-445.
[43] Lester Randolph Ford Jr, Delbert Ray Fulkerson. Maximal flow through a network. Research Memorandum RM-1400. The RAND Corporation: Santa Monica, California, 1954.
[44] T.E. Harris, F.S. Ross. Fundamentals of a Method for Evaluating Rail Net Capacities. Research Memorandum RM-1573. The RAND Corporation: Santa Monica, California, 1955.
[45] E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl. 1970, 11, 1277-1280.
[46] Jack Edmonds, Richard Manning Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (2). 1972, 19, 248-264.
[47] Andrew V. Goldberg. A New Max-Flow Algorithm. Technical Report TM-291. Laboratory for Computer Science, M.I.T, 1985.
[48] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms. MIT Press, 1990.
[49] S. Even, A. Itai, A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. Society for Industrial and Applied Mathematics (5). 1976, 4, 691-703.