Фрэнк Харрис

Фрэнк Харрис
Фрэнк Харари (слева) и Клаус Вагнер в Обервольфахе, 1972 год.
Рожденный ( 1921-03-11 ) 11 марта 1921 г.
Нью-Йорк , Нью-Йорк , США
Умер 4 января 2005 г. ) ( 2005-01-04 ) ( 83 года
Лас-Крусес, Нью-Мексико , США
Национальность Американский
Альма-матер Бруклинский колледж
Калифорнийский университет, Беркли
Известный Граф Гольднера – Харари
Обобщенные крестики-нолики Харари
Научная карьера
Поля Математика
Учреждения Мичиганский университет
Государственный университет Нью-Мексико
Докторантура Альфред Л. Фостер

Фрэнк Харари (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] В момент его смерти в Лас-Крусесе другие сотрудники кафедры компьютерных наук почувствовали утрату великого ума, который когда-то работал рядом с ними. Заведующий кафедрой компьютерных наук на момент смерти Харари Деш Ранджан сказал: «Доктор Харари был настоящим ученым с искренней любовью к теории графов, которая была бесконечным источником новых открытий, красоты, любопытства и сюрпризов. и радость за него до самого конца его жизни».

Математика [ править ]

Работы Харари по теории графов были разнообразными. Некоторые темы, которые его очень интересовали, были:

  • Перечисление графов , то есть подсчет графов заданного вида. [7] Он стал соавтором книги на эту тему (Harary and Palmer 1973). Основная трудность состоит в том, что два изоморфных графа не следует считать дважды; таким образом, необходимо применить теорию счета Пойа при групповом действии. Харари был в этом экспертом.
  • Подписанные графики . Харари изобрел эту ветвь теории графов. [8] [9] которая выросла из проблемы теоретической социальной психологии, исследованной психологами Дорвином Картрайт и Харари. [10]
  • Приложения теории графов во многих областях, особенно в социальных науках, таких как теория баланса , динамика мнений и теория турниров . [11] Харари был соавтором первой электронной книги Джона Уайли «Теория графов и география» .

Среди более чем 700 научных статей, написанных Харари, две были написаны в соавторстве с Полом Эрдешем , что дало Харари номер Эрдеша 1. [12] Он много читал лекции и вел алфавитные списки городов, в которых выступал.

Самая известная классическая книга Харари «Теория графов» была опубликована в 1969 году и представляла собой практическое введение в область теории графов. Очевидно, что Харари в этой книге, как и в других своих публикациях, сосредоточил внимание на разнообразном и разнообразном применении теории графов в других областях математики, физики и многих других. В предисловии к «Теории графов» Харари отмечает...

« ...теория графов находит применение в некоторых областях физики, химии, коммуникативных наук, компьютерных технологий, электротехники и гражданского строительства, архитектуры, операционных исследований, генетики, психологии, социологии, экономики, антропологии и лингвистики » . [13]

Харари быстро начал продвигать обучение, основанное на исследованиях, через свои тексты, о чем свидетельствует его ссылка на традицию метода Мура . Харари внес много уникальных вкладов в теорию графов, исследуя все больше и больше различных областей исследований и успешно пытаясь связать их с теорией графов. Классическая книга Харари «Теория графов» начинается с предоставления читателю большей части необходимых знаний об основных графах, а затем погружается прямо в доказательство разнообразия содержания, которое содержится в теории графов. Некоторые другие математические области, которые Харари напрямую связывает с теорией графов в своей книге, начинают появляться примерно в главе 13, эти темы включают линейную алгебру и абстрактную алгебру .

Харари также внес влиятельный вклад в теорию социального обучения, используемую в социологии и поведенческой экономике, выведя критерий консенсуса в Джона Р.П. Френча . модели социальной власти [14] Этого на несколько десятилетий предвосхитила, хотя и в особом случае, широко используемая модель обучения ДеГрута .

Квадратный корень дерева [ править ]

Одной из причин изучения теории графов является ее применение к социограммам, описанным Джейкобом Л. Морено . Например, матрицу смежности социограммы использовал Леон Фестингер. [15] теории графов Фестингер отождествил клику с социальной кликой и исследовал диагональ куба матрицы смежности групп, чтобы обнаружить клики. Харари присоединился к Яну Россу, чтобы улучшить обнаружение клик Фестингера. [16]

Признание степеней матрицы смежности побудило Харари и Росс отметить, что полный граф можно получить из квадрата матрицы смежности дерева . Опираясь на свое исследование обнаружения клик, они описали класс графов, для которых матрица смежности представляет собой квадрат матрицы смежности дерева. [17]

  • Если граф G представляет собой квадрат дерева, то он имеет уникальный квадратный корень дерева.
  • Некоторый словарный запас, необходимый для понимания этого доказательства и использованных здесь методов, представлен в книге Харари «Квадрат дерева» : (кликва, однокликва, мультикликва, сокликва, соседство, соседство, точка разреза, блок).
  • Как определить, является ли некоторый граф G квадратом дерева .
Если граф G полон или удовлетворяет следующим 5 свойствам, то G = T 2
(i) Каждая точка G соседна и G связна.
(ii) Если две клики встречаются только в одной точке b, то существует третья клика, с которой они делят b и ровно еще одну точку.
(iii) Между кликами и мультикликальными точками b группы G существует соответствие 1-1 такое, что клика C(b), соответствующая b, содержит ровно столько мультикликальных точек, сколько клик содержит b.
(iv) Никакие две клики не пересекаются более чем в двух точках.
(v) Число пар клик, встречающихся в двух точках, на единицу меньше числа клик.
  • Алгоритм нахождения квадратного корня дерева графа G.
Шаг 1: Найдите все клики G.
Шаг 2: Пусть кликами G являются C 1 ,...,C n , и рассмотрим набор мультикликальных точек b 1 ,..., bn , соответствующих этим кликам в соответствии с условием iii. Элементы этого набора являются неконечными точками T. Найдите все попарные пересечения n клик и сформируйте граф S, соединяя точки b i и b j линией тогда и только тогда, когда соответствующие клики C i и C j пересекаются в двух точках. Тогда S является деревом по условию v.
Шаг 3: Для каждой клики C i группы G пусть n i — количество однокликальных точек. К дереву S, полученному на шаге 2, присоедините n i конечных точек к bi , получив искомое дерево T.

Получив рассматриваемое дерево, мы можем создать матрицу смежности для дерева T и проверить, действительно ли это то дерево, которое мы искали. Возведение в квадрат матрицы смежности T должно дать матрицу смежности для графа, изоморфного графу G, с которого мы начали. Вероятно, самый простой способ увидеть эту теорему в действии — это рассмотреть случай, упомянутый Харари в «Квадрате дерева». В частности, рассматриваемый пример описывает дерево, соответствующее графику K 5

« Рассмотрим дерево, состоящее из одной точки, соединенной со всеми остальными. Когда дерево возводится в квадрат, результатом является полный граф. Мы хотим проиллюстрировать... T 2 К 5 "

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

Библиография [ править ]

  • 1965: (совместно с Робертом З. Норманом и Дорвином Картрайтом), Структурные модели: введение в теорию ориентированных графов , Нью-Йорк: Уайли М.Р. 0184874
  • 1967: (редактор) Теория графов и теоретическая физика , Academic Press MR 0232694
  • 1969: Теория графов , Аддисон-Уэсли М.Р. 0256911
  • 1971: (редактор с Гербертом Уилфом ) Математические аспекты анализа электрических сетей , Труды SIAM-AMS, Том 3, Американское математическое общество , MR 0329788
  • 1973: (редактор) Новые направления в теории графов: материалы Анн-Арборской конференции 1971 года по теории графов , Мичиганский университет, Academic Press MR 0340065
  • 1973: (совместно с Эдгаром М. Палмером) Графическое перечисление , Academic Press MR 0357214
  • 1979: (редактор) «Темы теории графов» , Нью-Йоркская академия наук, MR 557879
  • 1984: (совместно с Пером Хаге) Структурные модели в антропологии , Кембриджские исследования в области социальной и культурной антропологии, издательство Кембриджского университета , MR 0738630
  • 1990: (с Фредом Бакли) Расстояние в графиках , Perseus Press MR 1045632
  • 1991: (совместно с Пером Хаге) Обмен в Океании: теоретико-графический анализ , Оксфордские исследования по социальной и культурной антропологии, Oxford University Press .
  • 2002: (совместно с Сандрой Лах Арлингхаус и Уильямом К. Арлингхаусом) Теория графов и география: интерактивная электронная книга , Джон Уайли и сыновья, MR 1936840
  • 2007: (совместно с Пером Хаге) Сети островов: структуры коммуникации, родства и классификации в Океании (структурный анализ в социальных науках) , Cambridge University Press.

Ссылки [ править ]

  1. ↑ Перейти обратно: Перейти обратно: а б [1] , биографический очерк на ACM SIGACT. сайте
  2. ↑ Фрэнк Харари, 1921–2005 гг. - Колумбийский университет. Архивировано 5 ноября 2013 г., в Wayback Machine.
  3. ^ О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Фрэнк Харари» , Архив истории математики MacTutor , Университет Сент-Эндрюс
  4. ^ «Донкихотское приключение Фрэнка Харари» , Michigan Daily , 16 апреля 1969 г.
  5. ↑ Куина Н. Ли-Чуа (13 октября 2001 г.) Отец современной теории графов , Philippine Daily Inquirer , ссылка из Google News
  6. ^ Альба, Диана М. (7 января 2005 г.). «Покойный профессор НМГУ сделал блестящую карьеру». Лас-Крусес Сан-Ньюс . п. 1А.
  7. ^ Харари, Франк (1955), «Число линейных, направленных, корневых и связных графов», Transactions of the American Mathematical Society , 78 (2): 445–463, doi : 10.1090/S0002-9947-1955-0068198- 2 , МР   0068198 .
  8. ^ Харари, Ф. (1953-54) «О понятии баланса знакового графа», Michigan Mathematical Journal 2: 143-146 и приложение, предшествующее стр. 1.
  9. ^ Ф. Харари (1955) О локальном балансе и N-балансе в подписанных графах , Michigan Mathematical Journal 3: ссылка с 37 по 41 из Project Euclid
  10. ^ Картрайт, Д.; Харари, Фрэнк (1956). «Структурный баланс: обобщение теории Хайдера» (PDF) . Психологический обзор . 63 (5): 277–293. дои : 10.1037/h0046049 . ПМИД   13359597 .
  11. ^ Харари, Фрэнк ; Мозер, Лео (1966), «Теория круговых турниров», American Mathematical Monthly , 73 (3): 231–246, doi : 10.2307/2315334 , JSTOR   2315334
  12. ^ Список людей по номеру Эрдеша
  13. ^ Фрэнк Харари (1969) Теория графов , Аддисон-Уэсли
  14. ^ Харари, Фрэнк (1959). Картрайт, Д. (ред.). Критерий единогласия в теории социальной власти Френча . Мичиганский университет. стр. 168–182.
  15. ^ Фестингер, Л. (1949) «Анализ социограмм с использованием матричной алгебры», Human Relations 2: 152–8.
  16. ^ Ф. Харари и Ян Росс (1957) «Процедура обнаружения клик с использованием групповой матрицы», Sociometry 20: 205–15 MR. 0110590
  17. ^ Ф. Харари и Ян Росс (1960)) Квадрат дерева, Технический журнал Bell System 39 (3): с 641 по 47 MR 0115937

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Frank_Harary&oldid=1190010827"