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