Графы ў інфарматыцы: вызначэнне, віды, прымяненне, прыклады. Тэорыя графаў у інфарматыцы

Графы ў інфарматыцы з'яўляюцца спосабам вызначэння адносін у сукупнасці элементаў. Гэта асноўныя аб'екты вывучэння тэорыі графаў.

базавыя вызначэння

З чаго складаецца граф у інфарматыцы? Ён уключае мноства аб'ектаў, званых вяршынямі або вузламі, некаторыя пары якіх звязаны т. Зв. рэбрамі. Напрыклад, граф на малюнку (а) складаецца з чатырох вузлоў, пазначаных А, У, З, і D, з якіх B злучаны з кожнай з трох іншых вяршыняў рэбрамі, а C і D таксама злучаныя. Два вузла з'яўляюцца суседнімі, калі яны злучаныя рубам. На малюнку паказаны тыповы спосаб таго, як будаваць графы па інфарматыцы. Кругі ўяўляюць вяршыні, а лініі, якія злучаюць кожную іх пару, з'яўляюцца рэбрамі.

Які граф называецца неориентированным ў інфарматыцы? У яго адносіны паміж двума канцамі рэбры з'яўляюцца сіметрычнымі. Рабро проста злучае іх адзін з адным. У многіх выпадках, аднак, неабходна выказаць асіметрычныя адносіны - напрыклад, тое, што A паказвае на B, але не наадварот. Гэтай мэты служыць вызначэнне графа ў інфарматыцы, па-ранейшаму складаецца з набору вузлоў разам з наборам арыентаваных рэбраў. Кожнае арыентаванае рабро ўяўляе сабой сувязь паміж вяршынямі, кірунак якой мае значэнне. Накіраваныя графы малююць так, як паказана на малюнку (b), рэбры іх прадстаўленыя стрэлкамі. Калі патрабуецца падкрэсліць, што граф ненаправленную, яго называюць неориентированным.

мадэлі сетак

Графы ў інфарматыцы служаць матэматычнай мадэллю сеткавых структур. На наступным малюнку прадстаўлена структура інтэрнэту, тады насіў назву ARPANET, у снежні 1970 года, калі яна мела толькі 13 кропак. Вузлы ўяўляюць сабой вылічальныя цэнтры, а рэбры злучаюць дзве вяршыні з прамой сувяззю паміж імі. Калі не звяртаць увагі на накладзеную карту ЗША, астатняя частка малюнка з'яўляецца 13-вузлавых графам, падобным папярэднім. Пры гэтым сапраўднае размяшчэнне вяршыняў неістотна. Важна, якія вузлы злучаныя адзін з адным.

Прымяненне графаў у інфарматыцы дазваляе ўявіць, як рэчы альбо фізічна, альбо лагічна звязаныя паміж сабой у сеткавай структуры. 13-вузлавой ARPANET з'яўляецца прыкладам камунікацыйнай сеткі, у якой вяршыні-кампутары або іншыя прылады могуць перадаваць паведамленні, а рэбры ўяўляюць сабой прамыя лініі сувязі, па якіх інфармацыя можа быць перададзена.

маршруты

Хоць графы прымяняюцца ў многіх розных галінах, яны валодаюць агульнымі рысамі. Тэорыя графаў (інфарматыка) уключае, магчыма, найважную з іх - ідэю аб тым, што рэчы часта перамяшчаюцца па рэбрах, паслядоўна пераходзячы ад вузла да вузла, няхай гэта будзе пасажыр некалькіх авіярэйсаў або інфармацыя, якая перадаецца ад чалавека да чалавека ў сацыяльнай сеткі, альбо карыстальнік кампутара, паслядоўна наведвае шэраг вэб-старонак, вынікаючы па спасылках.

Гэтая ідэя матывуе вызначэнне маршруту як паслядоўнасці вяршыняў, звязаных паміж сабой рэбрамі. Часам узнікае неабходнасць разглядаць маршрут, які змяшчае не толькі вузлы, але і паслядоўнасць рэбраў, іх злучаюць. Напрыклад, паслядоўнасць вяршыняў MIT, BBN, RAND, UCLA з'яўляецца маршрутам у графе інтэрнэту ARPANET. Праходжанне вузлоў і рэбраў можа быць паўторным. Напрыклад, SRI, STAN, UCLA, SRI, UTAH, MIT таксама з'яўляецца маршрутам. Шлях, у якім рэбры не паўтараюцца, называецца ланцугом. Калі ж не паўтараюцца вузлы, то ён носіць назву просты ланцуга.

цыклы

Асабліва важныя віды графаў у інфарматыцы - гэта цыклы, якія ўяўляюць сабой кальцавую структуру, такую як паслядоўнасць вузлоў LINC, CASE, CARN, HARV, BBN, MIT, LINC. Маршруты з, па меншай меры, трыма рэбрамі, у якіх першы і апошні вузел аднолькавыя, а астатнія розныя, ўяўляюць сабой цыклічныя графы ў інфарматыцы.

Прыклады: цыкл SRI, STAN, UCLA, SRI з'яўляецца самым кароткім, а SRI, STAN, UCLA, RAND, BBN, UTAH, SRI значна больш.

Фактычна кожнае рабро графа ARPANET належыць да цыклу. Гэта было зроблена наўмысна: калі якое-небудзь з іх выйдзе з ладу, застанецца магчымасць пераходу з аднаго вузла ў іншы. Цыклы ў сістэмах камунікацыі і транспарту прысутнічаюць для забеспячэння надмернасці - яны прадугледжваюць альтэрнатыўныя маршруты па іншым шляху цыклу. У сацыяльнай сеткі таксама часта прыкметныя цыклы. Калі вы выявіце, напрыклад, што блізкі школьны сябар кузена вашай жонкі на самай справе працуе з вашым братам, то гэта з'яўляецца цыклам, які складаецца з вас, вашай жонкі, яе стрыечнага брата, яго школьнага сябра, яго супрацоўніка (т. Е. Вашага брата) і, нарэшце, зноў вас.

Складны граф: вызначэнне (інфарматыка)

Натуральна задацца пытаннем, ці можна з кожнага вузла патрапіць у любы іншы вузел. Граф складны, калі паміж кожнай парай вяршыняў існуе маршрут. Напрыклад, сетка ARPANET - складны граф. Тое ж можна сказаць і пра большасць камунікацыйных і транспартных сетак, так як іх мэта складаецца ў тым, каб накіроўваць трафік ад аднаго вузла да іншага.

З іншага боку, няма ніякіх апрыёрных падстаў чакаць таго, што дадзеныя віды графаў у інфарматыцы шырока распаўсюджаныя. Напрыклад, у сацыяльнай сетцы нескладана прадставіць двух людзей, не звязаных паміж сабой.

кампаненты

Калі графы ў інфарматыцы не звязаныя, то яны натуральным чынам распадаюцца на набор звязаных фрагментаў, груп вузлоў, якія з'яўляюцца ізаляванымі і ня перасякальнымі. Напрыклад, на малюнку намаляваныя тры такія часткі: першая - А і В, другая - C, D і Е, і трэцяя складаецца з пакінутых вяршыняў.

Кампаненты складнасці графа ўяўляюць сабой падмноства вузлоў, у якіх:

• кожная вяршыня падгрупы мае маршрут да любой іншай;
• падмноства не з'яўляецца часткай некаторага большага набору, у якім кожны вузел мае маршрут да любога іншага.

Калі графы ў інфарматыцы падзяляюцца на іх кампаненты, то гэта з'яўляецца толькі пачатковым спосабам апісання іх структуры. У рамках дадзенага кампанента можа быць багатая ўнутраная структура, важная для інтэрпрэтацыі сеткі. Напрыклад, фармальным метадам вызначэння важнасці вузла з'яўляецца вызначэнне таго, на колькі частак падзеліцца граф, калі вузел будзе прыбраны.

максімальная кампанента

Існуе метад якаснай ацэнкі кампанентаў складнасці. Напрыклад, ёсць сусветная сацыяльная сетка з сувязямі паміж двума людзьмі, калі яны з'яўляюцца сябрамі.

Сувязная яна? Верагодна, няма. Звязнасць - даволі крохкае ўласцівасць, і паводзіны аднаго вузла (або невялікага іх набору) можа звесці яе на нішто. Напрыклад, адзін чалавек без якіх-небудзь жывых сяброў будзе кампанентам, якія складаюцца з адзінай вяршыні, і, такім чынам, граф не будзе сувязным. Або аддалены трапічны востраў, які складаецца з людзей, якія не маюць ніякага кантакту з навакольным светам, таксама будзе невялікі кампанентай сеткі, што пацвярджае яе няскладна.

Глабальная сетка сяброў

Але ёсць яшчэ сёе-тое. Напрыклад, чытач папулярнай кнігі мае сяброў, якія выраслі ў іншых краінах, і складае з імі адну кампаненту. Калі прыняць да ўвагі бацькоў гэтых сяброў і іх сяброў, то ўсе гэтыя людзі таксама знаходзяцца ў той жа кампаненце, хоць яны ніколі не чулі пра чытача, гавораць на іншай мове і побач з ім ніколі не былі. Такім чынам, хоць глабальная сетка дружбы - ня сувязная, чытач будзе ўваходзіць у кампанент вельмі вялікага памеру, які пранікае усе часткі свету, які ўключае ў сябе людзей з самых розных слаёў і, фактычна, які змяшчае значную частку насельніцтва зямнога шара.

Тое ж мае месца і ў сеткавых наборах даных - вялікія, складаныя сеткі часта маюць максімальную кампаненту, якая ўключае значную частку ўсіх вузлоў. Больш за тое, калі сетка ўтрымлівае максімальную кампаненту, яна амаль заўсёды толькі адна. Каб зразумець, чаму, варта вярнуцца да прыкладу з глабальнай сеткай дружбы і паспрабаваць ўявіць наяўнасць двух максімальных кампанент, кожная з якіх уключае мільёны людзей. Спатрэбіцца наяўнасць адзінага рэбры ад каго-небудзь з першай кампаненты да другой, каб дзве максімальныя кампаненты зліліся ў адну. Так як рабро адзінае, то ў большасці выпадкаў неверагодна, каб яно не ўтварылася, і, такім чынам, дзве максімальныя кампаненты ў рэальных сетках ніколі не назіраюцца.

У некаторых рэдкіх выпадках, калі дзве максімальныя кампаненты суіснавалі на працягу доўгага час у рэальнай сеткі, іх аб'яднанне было нечаканым, драматычным, і, у канчатковым выніку, мела катастрафічныя наступствы.

Катастрофа зліцця кампанент

Напрыклад, пасля прыбыцця еўрапейскіх даследчыкаў у цывілізацыі Заходняга паўшар'я прыкладна паўтысячагоддзя таму адбыўся глабальны катаклізм. З пункту гледжання сеткі гэта выглядала так: пять тысяч гадоў глабальная сацыяльная сетка, верагодна, складалася з двух гіганцкіх кампанент - адной ў Паўночнай і Паўднёвай Амерыцы, а другі - у Еўразіі. Па гэтай прычыне тэхналогіі развівалася незалежна ў двух кампанентах, і, што яшчэ горш, гэтак жа развіваліся і хваробы чалавека і т. Д. Калі дзве кампаненты, нарэшце, увайшлі ў кантакт, тэхналогіі і захворванні адной хутка і катастрафічна перапоўнілі другую.

Амерыканская сярэдняя школа

Паняцце максімальных кампанент карысна для разваг пра сетках і ў значна меншых памерах. Цікавы прыклад ўяўляе сабой граф, які ілюструе рамантычныя адносіны ў амерыканскай сярэдняй школе за 18-месячны перыяд. Той факт, што ён ўтрымлівае максімальную кампаненту, мае важнае значэнне, калі гаворка заходзіць пра распаўсюд захворванняў, што перадаюцца палавым шляхам, што і з'яўлялася мэтай праведзенага даследавання. Вучні, магчыма, мелі толькі аднаго партнёра за гэты перыяд часу, але, тым не менш, не ўсведамляючы гэтага, былі часткай максімальнай кампаненты і, такім чынам, часткай многіх маршрутаў патэнцыйнай перадачы. Гэтыя структуры адлюстроўваюць адносіны, якія, магчыма, даўно скончылася, але яны звязваюць індывідаў у ланцугах занадта доўга, каб стаць прадметам пільнай увагі і плётак. Тым не менш, яны рэальныя: як сацыяльныя факты гэта нябачныя, але лагічна вынікаюць макроструктуры, якія ўзніклі як прадукт індывідуальнага пасярэдніцтва.

Адлегласць і пошук у шырыню

У дадатак да звестак пра тое, ці звязаныя два вузла маршрутам, тэорыя графаў у інфарматыцы дазваляе даведацца і пра яго даўжыні - у транспарце, сувязі або пры распаўсюдзе навін і захворванняў, а таксама пра тое, ці праходзіць ён праз некалькі вяршыняў ці мноства.

Для гэтага варта вызначыць даўжыню маршруту, роўную ліку крокаў, якія ён утрымлівае ад пачатку да канца, т. Е. Лік рэбраў ў паслядоўнасці, якая яго складае. Напрыклад, маршрут MIT, BBN, RAND, UCLA мае даўжыню 3, а MIT, UTAH - 1. Выкарыстоўваючы даўжыню шляху, можна казаць пра тое, ці размешчаны два вузла ў графе блізка адзін да аднаго ці далёка: адлегласць паміж двума вяршынямі вызначаецца як даўжыня самага кароткага шляху паміж імі. Напрыклад, адлегласць паміж LINC і SRI роўна 3, хоць, каб пераканацца ў гэтым, варта пераканацца ў адсутнасці даўжыні, роўнай 1 ці 2, паміж імі.

Алгарытм пошуку ў шырыню

Для невялікіх графаў адлегласць паміж двума вузламі падлічыць лёгка. Але для складаных з'яўляецца неабходнасць у сістэматычным метадзе вызначэння адлегласцяў.

Самым натуральным спосабам гэта зрабіць і, такім чынам, найбольш эфектыўным, з'яўляецца наступны (на прыкладзе глабальнай сеткі сяброў):

• Усе сябры абвяшчаюцца якія знаходзяцца на адлегласці 1.
• Усе сябры сяброў (не лічачы ўжо адзначаных) абвяшчаюцца якія знаходзяцца на адлегласці 2.
• Усе іх сябры (зноў жа, не лічачы пазначаных людзей) абвяшчаюцца выдаленымі на адлегласць 3.

Працягваючы такім чынам, пошук праводзяць у наступных пластах, кожны з якіх - на адзінку далей папярэдняга. Кожны новы пласт складаецца з вузлоў, якія яшчэ не ўдзельнічалі ў папярэдніх, і якія ўваходзяць у рабро з вяршыняй папярэдняга пласта.

Гэтая тэхніка называецца пошукам у шырыню, так як яна выконвае пошук па графу вонкі ад пачатковага вузла, у першую чаргу ахопліваючы бліжэйшыя. У дадатак да прадастаўлення спосабу вызначэння адлегласці, яна можа служыць карыснай канцэптуальнай асновай для арганізацыі структуры графа, а таксама таго, як пабудаваць граф па інфарматыцы, размяшчаючы вяршыні на падставе іх адлегласці ад фіксаванай пачатковай кропкі.

Пошук у шырыню можа быць ужыты не толькі да сеткі сяброў, але і да любога графу.

свет цесны

Калі вярнуцца да глабальнай сеткі сяброў, можна ўбачыць, што аргумент, які тлумачыць прыналежнасць да максімальнай кампаненце, на самай справе сцвярджае нешта большае: не толькі ў чытача ёсць маршруты да сяброў, якія злучаюць яго са значнай доляй насельніцтва зямнога шара, але гэтыя маршруты на здзіўленне кароткія .

Гэтая ідэя атрымала назву «феномену цеснага свету»: свет здаецца маленькім, калі думаць пра тое, які кароткі маршрут звязвае любых двух людзей.

Тэорыя «шасці поціскаў рукі» упершыню эксперыментальна даследавалася Стэнлі Милгрэмом і яго калегамі ў 1960-я гады. Не маючы якога-небудзь набору дадзеных сацыяльных сетак і з бюджэтам у 680 даляраў ён вырашыў праверыць папулярную ідэю. З гэтай мэтай ён папрасіў 296 выпадкова адабраных ініцыятараў паспрабаваць адаслаць ліст біржавым брокеру, які жыў у прыгарадзе Бостана. Ініцыятарам былі дадзены некаторыя асабістыя дадзеныя пра мэту (уключаючы адрас і прафесію), і яны павінны былі пераслаць ліст асобе, якога яны ведалі па імені, з тымі ж інструкцыямі, каб яно дасягнула мэты як мага хутчэй. Кожны ліст прайшло праз рукі шэрагу сяброў і ўтварыла ланцужок, якая замыкае на біржавых брокераў за межамі Бостана.

Сярод 64 ланцужкоў, якія дасягнулі мэты, сярэдняя даўжыня была роўная шасці, што пацвердзіла лік, названае два дзесяцігоддзі раней у назве п'есы Джона Гэран.

Нягледзячы на ўсе недахопы гэтага даследавання, эксперымент прадэманстраваў адзін з найважнейшых аспектаў нашага разумення сацыяльных сетак. У наступныя гады з яго быў зроблены больш шырокі выснову: сацыяльныя сеткі, як правіла, маюць вельмі кароткія маршруты паміж адвольнымі парамі людзей. І нават калі такія апасродкаваныя сувязі з кіраўнікамі прадпрыемстваў і палітычнымі лідэрамі не акупляюцца на штодзённай аснове, што існаваньне гэтых кароткіх маршрутаў гуляе вялікую ролю ў хуткасці распаўсюду інфармацыі, хвароб і іншых відаў заражэння ў грамадстве, а таксама ў магчымасцях доступу, якія сацыяльная сетка дае людзям з зусім процілеглымі якасцямі.