Фрэнк Харари (11 марта 1921 г. — 4 января 2005 г.) — американский математик , специализировавшийся на теории графов . Он был широко признан одним из «отцов» современной теории графов. [1] Харари был мастером ясного изложения и вместе со своими многочисленными аспирантами стандартизировал терминологию графов. Он расширил сферу применения этой области, включив в нее физику, психологию, социологию и даже антропологию. Одаренный острым чувством юмора, Харари бросал вызов и развлекал аудиторию на всех уровнях математической сложности. Особым трюком, который он использовал, было превращение теорем в игры — например, студенты пытались добавить красные ребра к графу на шести вершинах, чтобы создать красный треугольник, в то время как другая группа студентов пыталась добавить ребра, чтобы создать синий треугольник (и каждое ребро графа должно было быть либо синим, либо красным). Из-за теоремы о друзьях и незнакомцах одна или другая команда должна была победить.
Фрэнк Харари родился в Нью-Йорке , был старшим ребенком в семье еврейских иммигрантов из Сирии и России . Он получил степени бакалавра и магистра в Бруклинском колледже в 1941 и 1945 годах соответственно [2] и степень доктора философии под руководством Альфреда Л. Фостера в Калифорнийском университете в Беркли в 1948 году.
До начала преподавательской деятельности он работал научным сотрудником в Институте социальных исследований Мичиганского университета .
Первая публикация Харари, «Атомные булевоподобные кольца с конечным радикалом», была опубликована в Duke Mathematical Journal в 1950 году после многих усилий. Впервые эта статья была представлена Американскому математическому обществу в ноябре 1948 года, затем отправлена в Duke Mathematical Journal , где она была пересмотрена три раза, прежде чем была окончательно опубликована через два года после ее первоначальной отправки. [ необходима ссылка ] Харари начал свою преподавательскую карьеру в Мичиганском университете в 1953 году, где он сначала был доцентом, затем в 1959 году доцентом, а в 1964 году был назначен профессором математики , эту должность он занимал до 1986 года.
С 1987 года он был профессором (и почетным профессором-эмеритом ) на кафедре компьютерных наук в Университете штата Нью-Мексико в Лас-Крусес . Он был одним из основателей журнала « Journal of Combinatorial Theory» и журнала «Journal of Graph Theory» . [1]
В 1949 году Харари опубликовал работу «Об алгебраической структуре узлов» . Вскоре после этой публикации в 1953 году Харари опубликовал свою первую книгу (совместно с Джорджем Уленбеком) «О числе деревьев Хусими» . Именно после этого текста он начал приобретать всемирную известность за свои работы в области теории графов. В 1965 году была опубликована его первая книга « Структурные модели: введение в теорию направленных графов» , и до конца своей жизни он интересовался областью теории графов .
Начав свою работу в области теории графов около 1965 года, Харари начал покупать недвижимость в Энн-Арборе и делить купленные дома на квартиры. Это привело к критике за плохое обслуживание, «множество нарушений строительных норм» и шесть конфискаций зданий, которыми он владел. В газетной статье 1969 года цитировали Харари, который заявил: «Мы просто хотели эти объекты из-за стоимости земли... мы хотели выселить арендаторов», в то время как его жена Джейн заявила: «Мы хотели помочь бедным чернокожим найти лучшее жилье, но мы снова и снова попадали под удар». [3] [4] У Харари и его жены Джейн было шестеро детей: Мириам, Натали, Джудит, Томас, Джоэл и Чайя.
С 1973 по 2007 год Харари совместно написал еще пять книг, каждая из которых была посвящена теории графов. За время до своей смерти Харари путешествовал по миру, исследуя и публикуя более 800 статей (примерно с 300 различными соавторами) в математических журналах и других научных изданиях, больше, чем любой математик, кроме Пола Эрдоша. Харари записал, что он читал лекции в 166 разных городах по всем Соединенным Штатам и примерно в 274 городах в более чем 80 разных странах. Харари особенно гордился тем, что он читал лекции в городах по всему миру, начинающихся с каждой буквы алфавита, даже включая «X», когда он ездил в Ксантен , Германия. Харари также сыграл любопытную роль в отмеченном наградами фильме « Умница Уилл Хантинг » . В фильме были показаны опубликованные им формулы по перечислению деревьев, которые, как предполагалось, были чертовски сложными. [5]
В 1986 году в возрасте 65 лет Харари ушел на пенсию с должности профессора в Мичиганском университете. Однако Харари не отнесся к своему уходу на пенсию легкомысленно; после выхода на пенсию Харари был назначен заслуженным профессором компьютерных наук в Университете штата Нью-Мексико в Лас-Крусесе. Он занимал эту должность до своей смерти в 2005 году. В том же году, когда он вышел на пенсию, Харари стал почетным членом Национальной академии наук Индии; он также был редактором около 20 различных журналов, в основном посвященных теории графов и комбинаторной теории. Именно после выхода на пенсию Харари был избран почетным пожизненным членом Калькуттского математического общества и Южноафриканского математического общества.
Он умер в Мемориальном медицинском центре в Лас-Крусес, штат Нью-Мексико . [6] Во время его смерти в Лас-Крусес другие члены кафедры компьютерных наук чувствовали потерю великого ума, который когда-то работал рядом с ними. Глава кафедры компьютерных наук на момент смерти Харари Деш Ранджан сказал следующее: «Доктор Харари был настоящим ученым с искренней любовью к теории графов, которая была для него бесконечным источником новых открытий, красоты, любопытства, сюрпризов и радости до самого конца его жизни».
Работа Харари в области теории графов была разнообразной. Некоторые темы, которые представляли для него большой интерес:
Из более чем 700 научных статей, написанных Харари, две были написаны в соавторстве с Полом Эрдёшем , что дало Харари номер Эрдёша 1. [12] Он много читал лекции и вёл алфавитные списки городов, где выступал.
Самая известная классическая книга Харари «Теория графов» была опубликована в 1969 году и предлагала практическое введение в область теории графов. Очевидно, что внимание Харари в этой книге и среди других его публикаций было сосредоточено на разнообразном и многообразном применении теории графов в других областях математики, физики и многих других. Взятые из предисловия к «Теории графов», Харари отмечает...
« ...существуют приложения теории графов в некоторых областях физики, химии, коммуникационной науки, компьютерных технологий, электротехники и гражданского строительства, архитектуры, операционных исследований, генетики, психологии, социологии, экономики, антропологии и лингвистики » . [13]
Харари быстро начал продвигать обучение, основанное на исследовании, через свои тексты, что очевидно из его ссылок на традицию метода Мура . Харари внес много уникальных вкладов в теорию графов, поскольку он исследовал все больше и больше различных областей изучения и успешно пытался связать их с теорией графов. Классическая книга Харари «Теория графов» начинается с предоставления читателю большей части необходимых знаний об основных графах, а затем погружается прямо в доказательство разнообразия содержания, которое содержится в теории графов. Некоторые из других математических областей, которые Харари напрямую связывает с теорией графов в своей книге, начинают появляться около главы 13, эти темы включают линейную алгебру и абстрактную алгебру .
Харари также внес весомый вклад в теорию социального обучения, используемую в социологии и поведенческой экономике, выведя критерий консенсуса в модели социальной власти Джона Р. П. Френча . [14] Это предвосхитило на несколько десятилетий, хотя и в особом случае, широко используемую модель обучения ДеГроота .
Одной из мотиваций для изучения теории графов является ее применение к социограммам, описанным Джейкобом Л. Морено . Например, матрица смежности социограммы использовалась Леоном Фестингером. [15] Фестингер идентифицировал клику теории графов с социальной кликой и исследовал диагональ куба матрицы смежности групп для обнаружения клик. Харари объединился с Яном Россом, чтобы улучшить обнаружение клик Фестингера. [16]
Допущение степеней матрицы смежности привело Харари и Росса к выводу, что полный граф может быть получен из квадрата матрицы смежности дерева . Опираясь на свое исследование обнаружения клик, они описали класс графов, для которых матрица смежности является квадратом матрицы смежности дерева. [17]
Как только у нас есть нужное дерево, мы можем создать матрицу смежности для дерева T и проверить, что это действительно то дерево, которое мы искали. Возведение матрицы смежности T в квадрат должно дать матрицу смежности для графа, который изоморфен графу G, с которого мы начали. Вероятно, самый простой способ наблюдать эту теорему в действии — это наблюдать случай, который Харари упоминает в Квадрате дерева. В частности, рассматриваемый пример описывает дерево, соответствующее графу K 5
" Рассмотрим дерево, состоящее из одной точки, соединенной со всеми остальными. Когда дерево возводится в квадрат, результатом является полный граф. Мы хотим проиллюстрировать... T 2 K 5 "
Возведя в квадрат матрицу смежности ранее упомянутого дерева, мы можем заметить, что теорема действительно верна. Мы также можем заметить, что эта схема построения дерева, где «одна точка соединена со всеми остальными», всегда действительно даст правильное дерево для всех полных графов.
