Френк Харарі

Франк Харарі (зліва) і Клаус Вагнер^[en] в Обервольфах

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

Біографія

Франк Харарі народився в Нью-Йорку, в родині єврейських іммігрантів із Сирії та Марокко. Здобув ступінь бакалавра і магістра у Бруклінському коледжі 1941 і 1945 року відповідно[2], а також ступінь доктора філософії під керівництвом Альфреда Фостера^[en]  з Каліфорнійського університету у Берклі.

До початку своєї викладацької діяльності був науковим  асистентом в Інституті соціальних досліджень при Мічиганському університеті.

Перша публікація Харарі, «Атомні булеподібні кільця з кінцевим радикалом», потребувала багатьох зусиль, щоб потрапити у Duke Mathematical Journal^[en]. 1950 р. стаття була вперше представлена Американському математичному суспільству в листопаді 1948 року і врешті відіслана до Математичного Журналу, де була переглянута тричі, перш ніж бути опублікованою через два роки після її першої появи. Харарі розпочав свою викладацьку діяльність в Університеті штату Мічиган 1953 року, де був помічником професора, 1959 року доцентом, а 1964 року був призначений професором математики, обіймаючи посаду до 1986 року.

З 1987 року був професором (і заслуженим професором у відставці) в департаменті комп'ютерних наук у державному університеті Нью-Мехіко у Лас-Крузес.  Він був одним із засновників Journal of Combinatorial Theory^[en] і Journal of Graph Theory^[en].[1]

1949року Харарі опублікував статтю про алгебраїчну структуру вузлів. Незабаром після цієї публікації, 1953 року, Харарі опублікував свою першу книгу (спільно з Джорджем Уленбеком) про кількість дерев Хусімі. Після цього Харарі став відомим у світі завдяки своїм працям з теорії графів. 1965 року його перша книга «Структурна модель: вступ до теорії орієнтованих графів» була опублікована, і до кінця життя Харарі теорія графів була полем його досліджень.

Спочатку своєї праці в теорії графів, близько 1965, Харарі почав купувати власність в Енн-Арборі для збільшення доходів сім'ї.

Харарі з дружиною мали шістьох дітей: Міріам, Наталі, Джудіт, Томас, Джоель та Чоя. 1969 року в журналі «The Michigan Daily» була надрукована стаття, де обговорювалося питання оренди власності сім'єю Харарі.[3]

У період з 1973 до 2007 Харарі написав 5 спільних книг із теорії графів. У кінці життя він багато подорожував та публікував статті в математичних журналах та інших наукових виданнях. Харарі записав свої лекції у 166 різних містах Сполучених Штатів та 274 містах 80 країн світу. Харарі особливо пишався тим, що він читав лекції в містах по всьому світу, серед назв яких можна знайти кожну букву алфавіту, включаючи навіть «Х», коли він відправився в Ксантен, Німеччина. Харарі  також зіграв роль у фільмі «Добра Воля».  У фільмі показані формули, які він опублікував.[4]

У віці 65 років  Харарі пішов з Університету штату Мічиган.  Після виходу на пенсію Харарі був призначений заслуженим професором комп'ютерних наук державного університету в Лас-Крусес. Він обіймав цю посаду до своєї смерті.  2005 року, в рік виходу на пенсію, Харарі був почесним членом Національної академії наук Індії, також працював редактором близько 20 різних журналів, присвячених насамперед теорії графів і комбінаторній теорії. Харарі був обраний почесним довічним членом Калькуттського і Південноафриканського математичних товариств.

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

Математика

Робота Харарі з теорією графів була різноманітною. Деякі теми для нього були дуже цікавими:

• Перерахування графів підрахунок графів певного виду.[6] Він співавтор книги на цю тему (Харарі і Палмер 1973).  Основна складність полягає в тому, що два ізоморфні графи не повинні враховуватися двічі;

• підписані графи^[en] Харарі винайшов цю гілку теорії графів,[7][8] які виросли з проблеми теоретичної соціальної психології, що досліджували психолог Дорвін Картрайт і Харарі.[9]

• Теорія графів застосовується в різних галузях, особливо в галузі соціальних наук, таких, як теорія рівноваги і теорія турніру .[10] Харарі був співавтором першої електронної книги Джона Вілея з теорії графів і географії.

Серед більш ніж 700 наукових статей, написаних Харарі, дві були в співавторстві з Полом Ердосом, що дало Харарі число Ердеша.[11]Найвідоміша класична книга Харарі «Теорія графів» опублікована 1969 року і пропонувала практичне запровадження в галузі теорії графів.  Очевидно, що фокус Харарі в цій книзі і в інших його публікаціях акцентований на різноманітному застосуванні теорії графів в інших галузях математики, фізики та ін.  У передмові до «Теорії графів» Харарі зазначає:  «… є застосування теорії графів в деяких галузях фізики, хімії, зв'язку, комп'ютерної техніки, електротехніки та цивільного будівництва, архітектури, оперативних дослідженнях, генетики, психології, соціології, економіки, антропології і лінгвістики»[12].

Харарі зробив унікальний внесок  у теорію графів, досліджуючи все більше і більше різних галузей і  намагаючись пов'язати їх із  теорією графів.  Книга Харарі «Теорія графів» починається з надання читачеві більшої частини необхідних знань з теорії графів, а потім вражає різноманітністю змісту теорії. Деякі інші математичні галузі Харарі безпосередньо пов'язує з теорією графів у своїй книзі (глава 13), ці теми охоплюють лінійну алгебру і абстрактну алгебру. 

Квадратичне дерево

Однією з причин вивчення теорії графів було  застосування їх до соціограм^[en], описаних Якобом Л. Морено. Наприклад, матриця суміжності в соціограммі була використана Леоном Фестінґером.[13] Фестінґер ідентифікував теорію графів із соціальною клікою і досліджував діагональ куба матриці суміжності груп для виявлення кліків. Харарі разом з Аяном Россом об'єдналися, чим сприяли виявленню кліка Фестінґера.[14] Визнання повноважень матриці суміжності привели Харарі і Росса до того, що повний граф може бути отриманий з квадрата з матрицею суміжності дерева. Спираючись на вивчення виявлення клік, вони описали клас графів, для яких матриця суміжності є квадратом матриці суміжності дерева.[15]

• Якщо граф G є квадратом дерева, то вона має унікальний квадратний корінь дерева.
• Щоб зрозуміти використовувані методи і докази, необхідно мати на увазі специфічну термінологію.
•  Як визначити, чи є якийсь граф G  квадратом дерева.

  Якщо граф G є повним або задовольняє такі п'ять властивостей, тоді G = T^2 (і). Кожна точка G є сусідньою і зв'язною.   (||) Якщо два кліки зустрічаються тільки в одній точці b, тобто третя кліка, з якими вони поділяють b і одну іншу точку.   (III) Існує відповідність 1:1 між кліками та мультиклікальними точками b з G таким чином, що верхівка С (b), відповідно до b містить рівно стільки мультиклікальних точок, як і число клік, які включають b.   (IV) Ніякі дві кліки не перетинаються в більш ніж у двох точках.   (V) Число пар кліків, які зустрічаються в двох точках на одиницю менше, ніж число кліків.

• Алгоритм знаходження квадратного кореня дерева графу G.

Крок 1: Знайти всі кліки G. Крок 2: Нехай кліки G є C₁,…,C_n, і розглянемо набір мультиклікальних точок b₁,…,b_n, відповідні цим клікам до умови III.  Елементи цього ряду є неточними точками Т. Знайти всі попарні перетини n кліків і утворіть граф S шляхом приєднання точки b_i і b_j лінією, тоді і тільки тоді, коли відповідні кліки C_i і C_j перетинаються в двох точках, S є деревом за умовою   Крок 3 :. Для кожного кліка C_i з G, нехай ni — число одноточкових точок.  Для дерева S, отриманого на стадії 2, додайте n_i кінцевих точок до b_i, отримаємо дерево T.    Після того, як ми отримаємо дерево, ми можемо створити матрицю суміжності для дерева Т і перевірити, що це дійсно те дерево, яке ми шукали.  Квадрат матриці суміжності T повинен давати матрицю суміжності для графу, що є ізоморфним графу G, з якого ми почали.  Напевно, найпростіший спосіб спостерігати цю теорему в дії — спостерігати випадок, який Харари згадує у «Квадраті дерева» зокрема, приклад описує дерево, відповідне графу K₅ «Розглянемо дерево, що складається з однієї точки, з'єднаної з усіма іншими. Коли дерево квадратичне, то результатом буде повний граф. Ми хочемо проілюструвати  T^2${\displaystyle =}$K₅» . Після зведення в квадрат матриці суміжності  раніше згаданого дерева, ми можемо помітити, що ця теорема фактично виконується.  Ми можемо також відзначити, що ця модель створення дерева, де «одна точка з'єднана з усіма іншими», завжди дає правильне дерево для всіх повних графів.

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

• 1965: (with Robert Z. Norman and Dorwin Cartwright), Structural Models: An Introduction to the Theory of Directed Graphs. New York: Wiley MR0184874
• 1967: Graph Theory and Theoretical Physics, Academic Press MR0232694
• 1969: Graph Theory, Addison–Wesley MR0256911
• 1971: (editor with Herbert Wilf) Mathematical Aspects of Electrical Networks Analysis, SIAM-AMS Proceedings, Volume 3,American Mathematical Society MR0329788
• 1973: (editor) New Directions in the Theory of Graphs: Proceedings of the 1971 Ann Arbor Conference on Graph Theory, University of Michigan, Academic Press.MR0340065
• 1973: (with Edgar M. Palmer) Graphical Enumeration Academic Press MR0357214
• 1979: (editor) Topics in Graph Theory, New York Academy of Sciences MR557879
• 1984: (with Per Hage) Structural Models in Anthropology, Cambridge Studies in Social and Cultural Anthropology, Cambridge University Press MR0738630
• 1990: (with Fred Buckley) Distance in Graphs, Perseus Press MR1045632
• 1991: (with Per Hage) Exchange in Oceania: A Graph Theoretic Analysis, Oxford Studies in Social and Cultural Anthropology, Oxford University Press.
• 2002: (with Sandra Lach Arlinghaus & William C. Arlinghaus) Graph Theory and Geography: An Interactive E-Book, John Wiley and Sons MR1936840
• 2007: (with Per Hage) Island Networks: Communication, Kinship, and Classification Structures in Oceania (Structural Analysis in the Social Sciences), Cambridge University Press.

Див. також

• Граф Голднера — Харарі
• Узагальнені хрестики-нулики Харарі^[en]

Посилання

1. Frank Harary, a biographical sketch at the ACM SIGACT site
2. Frank Harary 1921—2005 — Columbia University [Архівовано 5 листопада 2013 у Wayback Machine.]
3. «The quixotic adventure of Frank Harary or how land speculation or city hall's neglect have contributed to Ann Arbor's low-income housing shortage», The Michigan Daily April 17, 1969, page 5
4. Queena N. Lee-Chua (October 13, 2001) The Father of Modern Graph Theory, Philippine Daily Inquirer, link from Google News
5. Alba, Diana M. (7 січня 2005). Late NMSU prof had noted career. Las Cruces Sun-News. с. 1A.
6. Harary, Frank (1955), Transactions of the American Mathematical Society, 78, doi:10.1090/S0002-9947-1955-0068198-2, MR 0068198 {{citation}}: Пропущений або порожній |title= (довідка).
7. Harary, F. (1953-54) «On the notion of balance of a signed graph», Michigan Mathematical Journal 2: 143—146 and addendum preceding p. 1.
8. F. Harary (1955) On local balance and N-balance in signed graphs, Michigan Mathematical Journal 3: 37 to 41 link from Project Euclid
9. Cartwright, D. and Harary, F. (1956)Structural balance: a generalization of Heider's theory, Psychological Review 63: 277—293 link from Stanford University
10. Harary, Frank; Moser, Leo (1966), The theory of round robin tournaments, American Mathematical Monthly, 73 (3): 231—246, doi:10.2307/2315334, JSTOR 2315334
11. List of people by Erdős number
12. Frank Harary (1969) Graph Theory, Addison–Wesley
13. Festinger, L. (1949) «The analysis of sociograms using matrix algebra», Human Relations 2: 152–8
14. F. Harary & Ian Ross (1957) «A procedure for clique detection using the group matrix», Sociometry 20: 205–15 MR0110590
15. F. Harary & Ian Ross (1960)) The square of a tree, Bell System Technical Journal 39(3):641 to 47 MR0115937

Примітки

• Френк Харарі(англ.) у проєкті «Математична генеалогія».
• Frank Harary memorial from New Mexico State University
• Джон Дж. О'Коннор та Едмунд Ф. Робертсон. Френк Харарі в архіві MacTutor (англ.)