Фрэнк Харари (11 марта 1921 — 4 января 2005) — американский математик , специализировавшийся на теории графов . Он был широко известен как один из «отцов» современной теории графов. [1] Харари был мастером ясного изложения и вместе со своими многочисленными докторантами стандартизировал терминологию графиков. Он расширил сферу применения этой области, включив в нее физику, психологию, социологию и даже антропологию. Обладая острым чувством юмора, Харари бросал вызов и развлекал публику любого уровня математической подготовки. Особый трюк, который он использовал, заключался в том, чтобы превратить теоремы в игры: например, студенты пытались добавить красные ребра к графу с шестью вершинами, чтобы создать красный треугольник, в то время как другая группа студентов пыталась добавить ребра, чтобы создать синий треугольник. (и каждое ребро графа должно было быть либо синим, либо красным). Из-за теоремы о друзьях и незнакомцах победа должна была бы прийти той или иной команде.
Фрэнк Харари родился в Нью-Йорке и был старшим ребенком в семье еврейских иммигрантов из Сирии и России . Он получил степени бакалавра и магистра в Бруклинском колледже в 1941 и 1945 годах соответственно [2] и докторскую степень. , под руководством Альфреда Л. Фостера из Калифорнийского университета в Беркли, 1948 год.
До своей преподавательской карьеры он работал научным сотрудником в Институте социальных исследований Мичиганского университета .
Первая публикация Харари «Атомные булевы кольца с конечным радикалом» претерпела немало усилий, чтобы быть помещенной в Duke Mathematical Journal в 1950 году. Эта статья была сначала представлена в Американское математическое общество в ноябре 1948 года, а затем отправлена в Duke Mathematical Journal. Журнал , в котором он трижды пересматривался, прежде чем был наконец опубликован через два года после первоначальной подачи. [ нужна цитация ] Харари начал свою преподавательскую карьеру в Мичиганском университете в 1953 году, где он был сначала доцентом, затем в 1959 году доцентом, а в 1964 году был назначен профессором математики , и занимал эту должность до 1986 года.
С 1987 года он был профессором (и заслуженным профессором ) факультета компьютерных наук Университета штата Нью-Мексико в Лас-Крусес . Он был одним из основателей « Журнала комбинаторной теории» и «Журнала теории графов» . [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 "
Возведя в квадрат матрицу смежности ранее упомянутого дерева, мы можем заметить, что теорема действительно верна. Мы также можем заметить, что этот шаблон построения дерева, в котором «одна точка соединена со всеми остальными», всегда действительно дает правильное дерево для всех полных графов.
