Перегляд вихідного коду сторінки Френк Харарі

{{вичитати}}
[[Файл:Wagner and Harary.jpg|міні|Франк Харарі (зліва) і {{Нп|Клаус Вагнер|||Klaus Wagner}} в Обервольфах]]
'''Франк Харарі''' (11 березня 1921&nbsp;— 4 січня 2005)&nbsp;— американський [[математик]], який спеціалізувався на [[Теорія графів|теорії графів]].&nbsp; Він був широко визнаний одним із «батьків» сучасної теорії графів.<ref name="sigact">[http://sigact.acm.org/harary.htm Frank Harary], a biographical sketch at the ACM [[SIGACT]] site</ref>
Харарі був майстром чіткого викладу і разом зі своїми численними докторантами стандартизував термінологію графів. Він розширював межі цієї галузі, включаючи фізику, психологію, соціологію і навіть антропологію. Обдарований, з тонким почуттям гумору, Харарі ставив під сумнів і розважав глядачів усіма можливими рівнями математичних суджень.&nbsp; Особливий трюк він використовував для того, щоб обернути теореми в ігри&nbsp;— наприклад, студенти намагаються додати червоні ребра до графу, щоб створити червоний трикутник, натомість інша група студентів намагалася додати ребра, щоб створити синій трикутник&nbsp; (і кожне ребро графу повинно було бути або синім, або червоним).  Завдяки [[Теорема про друзів і незнайомців|теоремі про друзів і незнайомців]], одна з команд вигравала.

== Біографія ==
Франк Харарі народився в [[Нью-Йорк]]у, в родині [[Євреї|єврейських]] іммігрантів із [[Сирія|Сирії]] та [[Марокко]]. Здобув ступінь бакалавра і магістра у [[Бруклінський коледж|Бруклінському коледжі]] 1941 і 1945 року відповідно<ref>[http://www1.cs.columbia.edu/~sanders/graphtheory/harary.html Frank Harary 1921—2005&nbsp;— Columbia University] {{webarchive |url=https://web.archive.org/web/20131105120806/http://www1.cs.columbia.edu/~sanders/graphtheory/harary.html |date=5 листопада 2013 }}</ref>, а також ступінь [[Доктор філософії|доктора філософії]] під керівництвом {{Нп|Альфреда Фостера|Альфреда Фостера||Alfred Foster}}  з [[Університет Каліфорнії (Берклі)|Каліфорнійського університету у Берклі]].

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

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

З 1987 року був [[професор]]ом (і [[Емеритура|заслуженим професором у відставці]]) в департаменті комп'ютерних наук у [[Державний університет Нью-Мехіко|державному університеті Нью-Мехіко]] у [[Лас-Крусес|Лас-Крузес]].  Він був одним із засновників {{Нп|Journal of Combinatorial Theory|||}} і {{Нп|Journal of Graph Theory|||}}.<ref name=sigact>[http://sigact.acm.org/harary.htm Frank Harary], a biographical sketch at the ACM [[SIGACT]] site</ref>

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

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

Харарі з дружиною мали шістьох дітей: Міріам, Наталі, Джудіт, Томас, Джоель та Чоя. 1969 року в журналі «The Michigan Daily» була надрукована стаття, де обговорювалося питання оренди власності сім'єю Харарі.<ref>«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</ref>

У період з 1973 до 2007 Харарі написав 5 спільних книг із теорії графів. У кінці життя він багато подорожував та публікував статті в математичних журналах та інших наукових виданнях. Харарі записав свої лекції у 166 різних містах Сполучених Штатів та 274 містах 80 країн світу. Харарі особливо пишався тим, що він читав лекції в містах по всьому світу, серед назв яких можна знайти кожну букву алфавіту, включаючи навіть «Х», коли він відправився в [[Ксантен]], Німеччина. Харарі  також зіграв роль у фільмі «[[Добра Воля]]».  У фільмі показані формули, які він опублікував.<ref>Queena N. Lee-Chua (October 13, 2001) [https://news.google.com/newspapers?nid=2479&dat=20011013&id=H6hjAAAAIBAJ&sjid=hiUMAAAAIBAJ&pg=2902,20087044&hl=en The Father of Modern Graph Theory], [[Philippine Daily Inquirer]], link from [[Google News]]</ref>

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

Він помер у [[Memorial Medical Center (Las Cruces)|Меморіальному медичному центрі]] [[Лас-Крусес]], [[Нью-Мехіко]].<ref>
{{cite news
 | first = Diana M.
 | last = Alba
 | title = Late NMSU prof had noted career
 | work = Las Cruces Sun-News
 | date = 2005-01-07
 | page = 1A
 }}</ref> Після його смерті в Лас-Крусес інші члени кафедри комп'ютерних наук відчули цю неймовірну втрату великого розуму, що колись працював поруч з ними.  Керівник відділу обчислювальної техніки Деш Ранджан сказав: «Доктор Харарі був справжнім ученим зі справжньою любов'ю до теорії графів, що була нескінченним джерелом нових відкриттів, краси, цікавості, сюрпризів  і радощів для нього до самого кінця його життя».

== Математика ==
Робота Харарі з теорією графів була різноманітною. Деякі теми для нього були дуже цікавими:
* [[Перерахування графів]] підрахунок графів певного виду.<ref>{{citation
 | last = Harary | first = Frank | author-link = Френк Харарі
 | doi = 10.1090/S0002-9947-1955-0068198-2
 | journal = [[Transactions of the American Mathematical Society]]
 | mr = 0068198 | volume = 78
 | year = 1955}}.</ref> Він співавтор книги на цю тему (Харарі і Палмер 1973).  Основна складність полягає в тому, що два ізоморфні графи не повинні враховуватися двічі;

* {{Нп|підписаний граф|підписані графи|| signed graphs}} Харарі винайшов цю гілку теорії графів,<ref>Harary, F. (1953-54) «On the notion of balance of a signed graph», [[Michigan Mathematical Journal]] 2: 143—146 and addendum preceding p. 1.</ref><ref>F. Harary (1955) [http://projecteuclid.org/euclid.mmj/1031710532 On local balance and N-balance in signed graphs], ''Michigan Mathematical Journal'' 3: 37 to 41 link from Project Euclid</ref> які виросли з проблеми теоретичної соціальної психології, що досліджували психолог [[Dorwin Cartwright|Дорвін Картрайт]] і Харарі.<ref>Cartwright, D. and Harary, F. (1956)[http://snap.stanford.edu/class/cs224w-readings/cartwright56balance.pdf Structural balance: a generalization of Heider's theory], [[Psychological Review]] 63: 277—293 link from [[Stanford University]]</ref>

* Теорія графів застосовується в різних галузях, особливо в галузі соціальних наук, таких, як теорія рівноваги і [[Турнір (теорія графів)|теорія турніру]] .<ref>{{citation
 | last1 = Harary | first1 = Frank | author1-link = Френк Харарі
 | last2 = Moser | first2 = Leo | author2-link = Leo Moser
 | doi = 10.2307/2315334
 | issue = 3
 | journal = [[American Mathematical Monthly]]
 | pages = 231–246
 | title = The theory of round robin tournaments
 | volume = 73
 | year = 1966
 | jstor = 2315334}}</ref> Харарі був співавтором першої [[Електронна книга|електронної книги]] Джона Вілея з теорії графів і географії.
Серед більш ніж 700 наукових статей, написаних Харарі, дві були в співавторстві з [[Пал Ердеш|Полом Ердосом]], що дало Харарі число Ердеша.<ref>[[List of people by Erdős number]]</ref>Найвідоміша класична книга Харарі «Теорія графів» опублікована 1969 року і пропонувала практичне запровадження в галузі теорії графів.  Очевидно, що фокус Харарі в цій книзі і в інших його публікаціях акцентований на різноманітному застосуванні теорії графів в інших галузях математики, фізики та ін.  У передмові до «Теорії графів» Харарі зазначає:  «… є застосування теорії графів в деяких галузях фізики, хімії, зв'язку, комп'ютерної техніки, електротехніки та цивільного будівництва, архітектури, оперативних дослідженнях, генетики, психології, соціології, економіки, антропології і лінгвістики»<ref>Frank Harary (1969) ''Graph Theory'', [[Addison–Wesley]]</ref>.

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

== Квадратичне дерево ==
Однією з причин вивчення теорії графів було  застосування їх до {{Нп|соціограмма|соціограм||sociogram}}, описаних [[Якоб Морено|Якобом Л. Морено]]. Наприклад, [[матриця суміжності]] в соціограммі була використана [[Леон Фестінґер|Леоном Фестінґером]].<ref>Festinger, L. (1949) «The analysis of sociograms using matrix algebra», ''Human Relations'' 2: 152–8</ref> Фестінґер ідентифікував теорію графів із соціальною [[Кліка (теорія графів)|клікою]] і досліджував діагональ куба матриці суміжності груп для виявлення кліків. Харарі разом з Аяном Россом об'єдналися, чим сприяли виявленню кліка Фестінґера.<ref>F. Harary & Ian Ross (1957) «A procedure for clique detection using the group matrix», ''Sociometry'' 20: 205–15 {{mr|id=0110590}}</ref>
Визнання повноважень матриці суміжності привели Харарі і Росса до того, що [[повний граф]] може бути отриманий з квадрата з матрицею суміжності [[Дерево (структура даних)|дерева]]. Спираючись на вивчення виявлення клік, вони описали клас графів, для яких матриця суміжності є квадратом матриці суміжності дерева.<ref>F. Harary & Ian Ross (1960)) The square of a tree, [[Bell System Technical Journal]] 39(3):641 to 47 {{mr|id=0115937}}</ref>
* Якщо граф G є квадратом дерева, то вона має унікальний квадратний корінь дерева.
* Щоб зрозуміти використовувані методи і докази, необхідно мати на увазі специфічну термінологію.
*  Як визначити, чи є якийсь граф G  квадратом дерева.
  Якщо граф G є повним або задовольняє такі п'ять властивостей, тоді G = T<sup>2</sup> (і). Кожна точка G є сусідньою і зв'язною.
  (||) Якщо два кліки зустрічаються тільки в одній точці b, тобто третя кліка, з якими вони поділяють b і одну іншу точку.
  (III) Існує відповідність 1:1 між кліками та мультиклікальними точками b з G таким чином, що верхівка С (b), відповідно до b містить рівно стільки мультиклікальних точок, як і число клік, які включають b.
  (IV) Ніякі дві кліки не перетинаються в більш ніж у двох точках.
  (V) Число пар кліків, які зустрічаються в двох точках на одиницю менше, ніж число кліків.
* Алгоритм знаходження квадратного кореня дерева графу G.
Крок 1: Знайти всі кліки G.
Крок 2: Нехай кліки G є C<sub>1</sub>,…,C<sub>n</sub>, і розглянемо набір мультиклікальних точок b<sub>1</sub>,…,b<sub>n</sub>, відповідні цим клікам до умови III.  Елементи цього ряду є неточними точками Т. Знайти всі попарні перетини n кліків і утворіть граф S шляхом приєднання точки b<sub>i</sub> і b<sub>j</sub> лінією, тоді і тільки тоді, коли відповідні кліки C<sub>i</sub> і C<sub>j</sub> перетинаються в двох точках, S є деревом за умовою
  Крок 3 :. Для кожного кліка C<sub>i</sub> з G, нехай ni&nbsp;— число одноточкових точок.  Для дерева S, отриманого на стадії 2, додайте n<sub>i</sub> кінцевих точок до b<sub>i</sub>, отримаємо дерево T.   
Після того, як ми отримаємо дерево, ми можемо створити матрицю суміжності для дерева Т і перевірити, що це дійсно те дерево, яке ми шукали.  Квадрат матриці суміжності T повинен давати матрицю суміжності для графу, що є ізоморфним графу G, з якого ми почали.  Напевно, найпростіший спосіб спостерігати цю теорему в дії&nbsp;— спостерігати випадок, який Харари згадує у «Квадраті дерева» зокрема, приклад описує дерево, відповідне графу K<sub>5</sub>
«Розглянемо дерево, що складається з однієї точки, з'єднаної з усіма іншими. Коли дерево квадратичне, то результатом буде повний граф. Ми хочемо проілюструвати  T<sup>2</sup><math>=</math>K<sub>5</sub>» .
Після зведення в квадрат матриці суміжності  раніше згаданого дерева, ми можемо помітити, що ця теорема фактично виконується.  Ми можемо також відзначити, що ця модель створення дерева, де «одна точка з'єднана з усіма іншими», завжди дає правильне дерево для всіх повних графів.

== Бібліографія ==
* 1965: (with Robert Z. Norman and Dorwin Cartwright), ''Structural Models: An Introduction to the Theory of Directed Graphs''. New York: Wiley MR[http://www.ams.org/mathscinet-getitem?mr=0184874 0184874]
* 1967: ''Graph Theory and Theoretical Physics'', Academic Press MR[http://www.ams.org/mathscinet-getitem?mr=0232694 0232694]
* 1969: ''Graph Theory'', Addison–Wesley MR[http://www.ams.org/mathscinet-getitem?mr=0256911 0256911]
* 1971: (editor with Herbert Wilf) ''Mathematical Aspects of Electrical Networks Analysis'', SIAM-AMS Proceedings, Volume 3,American Mathematical Society MR[http://www.ams.org/mathscinet-getitem?mr=0329788 0329788]
* 1973: (editor) ''New Directions in the Theory of Graphs: Proceedings of the 1971 Ann Arbor Conference on Graph Theory'', University of Michigan, Academic Press.MR[http://www.ams.org/mathscinet-getitem?mr=0340065 0340065]
* 1973: (with Edgar M. Palmer) ''Graphical Enumeration'' Academic Press MR[http://www.ams.org/mathscinet-getitem?mr=0357214 0357214]
* 1979: (editor) ''Topics in Graph Theory'', New York Academy of Sciences MR[http://www.ams.org/mathscinet-getitem?mr=557879 557879]
* 1984: (with Per Hage) ''Structural Models in Anthropology'', Cambridge Studies in Social and Cultural Anthropology, Cambridge University Press MR[http://www.ams.org/mathscinet-getitem?mr=0738630 0738630]
* 1990: (with Fred Buckley) ''Distance in Graphs'', Perseus Press MR[http://www.ams.org/mathscinet-getitem?mr=1045632 1045632]
* 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 MR[http://www.ams.org/mathscinet-getitem?mr=1936840 1936840]
* 2007: (with Per Hage) ''Island Networks: Communication, Kinship, and Classification Structures in Oceania (Structural Analysis in the Social Sciences)'', Cambridge University Press.

== Див. також ==
* [[Граф Голднера — Харарі]]
* {{Нп|Узагальнені хрестики-нулики Харарі|Узагальнені хрестики-нулики Харарі||Harary's generalized tic-tac-toe}}

== Посилання ==
{{примітки}}

== Примітки ==
* {{MathGenealogy|id=7684}}
* [http://www.cs.nmsu.edu/fnh/  Frank Harary memorial] from [[New Mexico State University]]
* {{MacTutor|id=Harary}}

{{Бібліоінформація}}
{{DEFAULTSORT:Харарі Френк}}
[[Категорія:Випускники Бруклінського коледжу]]
[[Категорія:Випускники Університету Каліфорнії у Берклі]]
[[Категорія:Уродженці Нью-Йорка]]