* * *
ПИОНЕРЫ ТЕОРИИ ГРАФОВ
Развитию теории графов в немалой степени способствовали такие выдающиеся ученые, как Уильям Томас Татт, Фрэнк Харари, Эдсгер Вибе Дейкстра и Пол Эрдёш. Теория графов приобрела большую известность благодаря их исследованиям, нестандартным задачам и написанным ими справочникам.
Британский ученый Уильям Томас Татт (1917–2002) изучал химию, но интерес к занимательным математическим задачам заставил его сменить сферу деятельности. В итоге в 1948 году он получил степень доктора математики и начал заниматься преподаванием и научной деятельностью. Во время Второй мировой войны он внес огромный вклад в расшифровку немецких кодов. Его 168 статей и несколько блестящих книг особенно обогатили теорию графов, а вместе с ней — комбинаторику и дискретную математику. Многие понятия теории графов теперь носят его имя.
Американец Фрэнк Харари (1921–2005) по праву считается основателем современной теории графов. Его 700 статей, выступления на конференциях в 87 странах, основанный им в 1977 году престижный «Журнал теории графов» и его «Теория графов», вышедшая в 1969 году, считающаяся одной из самых значимых книг по этой теме, являются доказательством тому, что он заслужил международное признание. Он применял теорию графов не только в математике и информатике, но также и в антропологии, географии, лингвистике, искусстве, музыке, физике, инженерном деле, исследовании операций и других областях.
Голландский ученый Эдсгер Вибе Дейкстра (1930–2002) заинтересовался компьютерными программами в раннем возрасте и посвятил им всю свою жизнь. Он работал в Голландии, а начиная с 1970 года — в Техасском университете в Остине. В 1972 году он был удостоен престижной премии Тьюринга за фундаментальный вклад в развитие языков программирования. Ему мы обязаны знаменитой фразой «Информатика не более наука о компьютерах, чем астрономия — наука о телескопах». Дейкстра никогда не пользовался компьютером, кроме как для отправки электронной почты и поиска информации в интернете, а все свои труды об алгоритмах и языках программирования он писал… от руки!
Пол Эрдёш (1913–1996) родился и получил образование в Будапеште. За свою жизнь он написал больше работ и сотрудничал с большим числом соавторов, чем любой другой математик XX столетия. Благодаря выдающемуся уму он добился исключительных результатов в теории графов, комбинаторике, геометрии и теории чисел. Он стал автором множества удивительных задач и гипотез, а также написал свыше 1500 статей. Эрдёш был атеистом, но (возможно, не без иронии) утверждал, что где-то в мироздании существует книга, в которой содержатся самые красивые математические доказательства. Безусловно, ученый внес неизмеримый вклад в написание этой книги.
* * *
Граф определяется множеством точек (которые также называются вершинами, или узлами графа) и множеством ребер, или дуг графа, которые соединяют его вершины попарно.
На рисунке выше представлены нулевой граф, состоящий из изолированных вершин; полный граф с тремя вершинами и тремя ребрами; граф с шестью вершинами и восьмью ребрами. Две вершины, соединенные ребром, называются смежными. Два ребра, которые имеют общую концевую вершину (инцидентные этой вершине), также называются смежными. Степенью вершины графа называется число инцидентных ей ребер.
Если вершинам графа сопоставить буквы, числа или некую другую информацию, то говорят, что такой граф является помеченным. Если ребрам графа поставлены в соответствие некие веса, такой граф называется взвешенным. Если на ребра графа нанести стрелки, обозначающие направления, то эти ориентированные ребра графа будут называться дугами. Если все ребра графа являются ориентированными, то такой граф называется ориентированным, или орграфом.
Графы также можно представить в виде списков, таблиц и различных выражений. Вершины графа можно изобразить в виде точек, окружностей, треугольников, а ребра — в виде прямых отрезков или фигурно изогнутых линий. Учитывая подобное разнообразие, важно уметь определять, когда два представления графа являются эквивалентными (изоморфными). Эквивалентные представления графа содержат одинаковые вершины и одинаковые связи между ними. Иными словами, между вершинами и ребрами двух представлений должно существовать взаимно однозначное соответствие, такое что степени вершин в обоих случаях будут одинаковы.