Фрэнк Харари - Frank Harary

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

Фрэнк Харари (11 марта 1921 - 4 января 2005) был американцем математик, которые специализировались на теория графов. Он был широко известен как один из «отцов» современной теории графов.[1]Харари был мастером четкого изложения и вместе со своими многочисленными докторантами стандартизировал терминологию графиков. Он расширил охват этой области, включив в нее физику, психологию, социологию и даже антропологию. Обладая острым чувством юмора, Харари бросал вызов и развлекал аудиторию на всех уровнях математической сложности. Особый трюк, который он использовал, состоял в том, чтобы превратить теоремы в игры - например, студенты пытались добавить красные ребра к графу с шестью вершинами, чтобы создать красный треугольник, в то время как другая группа студентов пыталась добавить ребра, чтобы создать синий треугольник. (и каждое ребро графа должно быть синим или красным). Из-за теорема о друзьях и незнакомцах, одна команда должна победить.

биография

Фрэнк Харари родился в Нью-Йорк, старший ребенок в семье Еврейский иммигранты из Сирия и Россия. Он получил степени бакалавра и магистра Бруклинский колледж в 1941 и 1945 годах соответственно[2] и его Кандидат наук., с руководителем Альфред Л. Фостер, из Калифорнийский университет в Беркли в 1948 г.

До своей педагогической карьеры он работал научным сотрудником Института социальных исследований университет Мичигана.

Первая публикация Харари «Атомные булевы кольца с конечным радикалом» претерпела много усилий, чтобы воплотить ее в Математический журнал герцога в 1950 г. Эта статья была впервые представлена ​​в Американское математическое общество в ноябре 1948 г., а затем отправлена ​​в Математический журнал герцога где он трижды пересматривался, прежде чем был окончательно опубликован через два года после его первоначального представления.[нужна цитата ] Харари начал свою педагогическую карьеру в Мичиганском университете в 1953 году, где он был сначала доцентом, затем в 1959 году доцентом, а в 1964 году был назначен на должность профессора. профессор по математике, эту должность он занимал до 1986 года.

С 1987 г. Профессор (и выдающийся Заслуженный профессор в отставке ) на кафедре компьютерных наук в Государственный университет Нью-Мексико в Лас-Крусес. Он был одним из основателей Журнал комбинаторной теории и Журнал теории графов.[1]

В 1949 году Харари опубликовал Об алгебраической структуре узлов. Вскоре после этой публикации в 1953 году Харари опубликовал свою первую книгу (совместно с Джорджем Уленбеком). О количестве деревьев Хусими. Следуя этому тексту, он начал завоевывать мировую репутацию за свои работы в области теории графов. В 1965 году его первая книга Структурные модели: введение в теорию ориентированных графов был опубликован, и всю оставшуюся жизнь его интересовала область Теория графов.

Начав свою работу в области теории графов примерно в 1965 году, Харари начал скупку собственности в Анн-Арбор чтобы пополнить доход своей семьи. У Харари и его жены Джейн было шестеро детей: Мириам, Натали, Джудит, Томас, Джоэл и Хая.

С 1973 по 2007 год Харари совместно написал еще пять книг, каждая из которых посвящена теории графов. Перед смертью Харари путешествовал по миру, исследуя и публикуя более 800 статей (с примерно 300 разными соавторами) в математических журналах и других научных публикациях, больше, чем любой другой математик, кроме Пола Эрдоша. Харари записал, что он читал лекции в 166 городах США и примерно в 274 городах более чем 80 стран. Харари особенно гордился тем, что читал лекции в городах по всему миру, начиная с каждой буквы алфавита, даже включая «X», когда он путешествовал по Ксантен, Германия. Харари также сыграл любопытную роль в отмеченном наградами фильме. Хорошая будет охота. В фильме были показаны опубликованные им формулы для подсчета деревьев, которые должны были быть чертовски трудными.[3]

В 1986 году в возрасте 65 лет Харари ушел с должности профессора в Мичиганском университете. Однако Харари нелегко отнесся к своему выходу на пенсию, после выхода на пенсию Харари был назначен Заслуженный профессор компьютерных наук в Государственном университете Нью-Мексико в Лас-Крусес. Он занимал эту должность до своей смерти в 2005 году. В том же году, когда вышел на пенсию, Харари стал почетным членом Национальной академии наук Индии, он также был редактором около 20 различных журналов, посвященных в основном теории графов и комбинаторной теории. . После выхода на пенсию Харари был избран пожизненным почетным членом Калькуттское математическое общество и Южноафриканского математического общества.

Он умер в Мемориальный медицинский центр в Лас-Крусес, Нью-Мексико.[4] Во время его смерти в Лас-Крусес другие сотрудники отдела компьютерных наук чувствовали потерю великого ума, который когда-то работал вместе с ними. Глава отдела компьютерных наук на момент смерти Харари Деш Ранджан сказал следующее: «Доктор Харари был настоящим ученым с искренней любовью к теории графов, которая была бесконечным источником новых открытий, красоты, любопытства, сюрпризов. и радость ему до самого конца его жизни ».

Математика

Работа Харари по теории графов была разнообразной. Его очень интересовали следующие темы:

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

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

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

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

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

Квадратный корень дерева

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

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

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

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

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

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

Библиография

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

Рекомендации

  1. ^ а б [1], биографический очерк в ACM SIGACT сайт
  2. ^ Фрэнк Харари 1921-2005 - Колумбийский университет В архиве 5 ноября 2013 г. Wayback Machine
  3. ^ Куина Н. Ли-Чуа (13 октября 2001 г.) Отец современной теории графов, Филиппинский Daily Inquirer, ссылка из Новости Google
  4. ^ Альба, Диана М. (2005-01-07). «Поздний профессор НМСУ отметил карьеру». Las Cruces Sun-News. п. 1А.
  5. ^ Харари, Фрэнк (1955), «Число линейных, ориентированных, корневых и связных графов», Труды Американского математического общества, 78: 445–463, Дои:10.1090 / S0002-9947-1955-0068198-2, МИСТЕР  0068198.
  6. ^ Харари, Ф. (1953-54) "О понятии баланса знакового графа", Мичиганский математический журнал 2: 143-146 и приложение к стр. 1.
  7. ^ Ф. Харари (1955) О локальном балансе и N-балансе в подписанных графиках, Мичиганский математический журнал 3: 37–41 ссылка из проекта Евклид
  8. ^ Картрайт, Д .; Харари, Фрэнк (1956). «Структурный баланс: обобщение теории Хайдера» (PDF). Психологический обзор. 63 (5): 277–293. Дои:10,1037 / ч0046049.
  9. ^ Харари, Фрэнк; Мозер, Лев (1966), «Теория круговых турниров», Американский математический ежемесячный журнал, 73 (3): 231–246, Дои:10.2307/2315334, JSTOR  2315334
  10. ^ Список людей по номеру Эрдёша
  11. ^ Фрэнк Харари (1969) Теория графов, Эддисон – Уэсли
  12. ^ Фестингер, Л. (1949) "Анализ социограмм с использованием матричной алгебры", Человеческие отношения 2: 152–8
  13. ^ Ф. Харари и Ян Росс (1957) "Процедура обнаружения клик с использованием групповой матрицы", Социометрия 20: 205–15 МИСТЕР0110590
  14. ^ Ф. Харари и Ян Росс (1960)) Квадрат дерева, Технический журнал Bell System 39 (3): с 641 по 47 МИСТЕР0115937

внешняя ссылка