Френк Харарі

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  Якщо граф G є повним або задовольняє наступним п'ятьом властивостям, тоді G = T² (і). Кожна точка 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²${\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.

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

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