Графики в информатиката: определение, типове, приложения, примери. Теория на графиките в компютърната наука

Графиките в информатиката са начин за дефиниране на взаимовръзките в комбинация от елементи. Това са основните предмети на обучение теория на графиките.

Основни дефиниции

Какво представлява графиката в компютърната наука? Тя включва набор от обекти, наречени върхове или възли, чиито двойки са свързани с така наречените. ребра. Например, графиката на фигура (а) се състои от четири възли, означени като А, В, С и D, от които В е свързан към всеки от другите три върха по краищата, а С и D също са свързани. Два възела са съседни, ако са свързани с ръб. Фигурата показва типичен начин за създаване на графики за компютърни науки. Кръговете представляват върховете, а линиите, свързващи всяка двойка от тях, са ребра.

Каква графика се нарича не-ориентирана в компютърните науки? Неговата връзка между двата края на реброто е симетрична. Ребрата ги свързва един към друг. В много случаи обаче е необходимо да се изразят асиметрични връзки - например, че А сочи към Б, но не обратното. Тази цел се определя от дефиницията на графика в информатиката, която все още се състои от набор от възли, заедно с набор от ориентирани ръбове. Всеки ориентиран край е връзка между върховете, чиято посока има стойност. Насочените графики са представени, както е показано на фигура (б), техните ръбове са представени със стрелки. Когато се налага да се подчертае, че графиката не е насочена, тя се нарича недиректно.

Модели на мрежите

Графиките в компютърната наука служат математически модел мрежови структури. Следващата фигура показва структурата на Интернет, наречена ARPANET, през декември 1970 г., когато имаше само 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 е свързана графика. Същото може да се каже и за повечето комуникационни и транспортни мрежи, тъй като целта им е да насочват трафика от един възел към друг.

От друга страна, няма a priori основание да се очаква, че тези графики в компютърната наука са широко разпространени. Например, в една социална мрежа не е трудно да си представим двама души, които не са свързани помежду си.

елементи

Ако графиките в компютърната наука не са свързани, те естествено се разпадат на съвкупност от свързани фрагменти, групи възли, които са изолирани и не се пресичат. Например, фигурата показва три такива части: първият - А и В, вторият - С, D и Е, а третият - останалите върхове.

Компонентите на свързването на графите са подмножество от възли, които имат:

• всеки връх на подгрупата има маршрут към всяка друга;
• Подмножество не е част от по-голям набор, в който всеки възел има маршрут към който и да е друг.

Когато графиките в компютърната наука са разделени на техните компоненти, това е само първоначалният начин за описване на тяхната структура. В рамките на този компонент може да има богата вътрешна структура, важна за интерпретацията на мрежата. Например, формален метод за определяне на значението на възел е да се определи колко части разделя графиката, ако се премахне възелът.

Максимален компонент

Съществува метод за качествена оценка на компонентите за свързване. Например, има световна социална мрежа с връзки между двама души, ако те са приятели.

Свързана ли е? Вероятно не. Свързаността е доста крехка собственост и поведението на един възел (или малък набор от тях) може да го унищожи. Например, един човек без живи приятели ще бъде компонент, състоящ се от един връх и следователно графиката няма да бъде свързана. Или отдалечен тропически остров, състоящ се от хора, които нямат контакт с външния свят, също ще бъде малък компонент на мрежата, което потвърждава несъответствието му.

Глобална мрежа от приятели

Но има и нещо друго. Например, читателят на една популярна книга има приятели, които са израснали в други страни и съставляват един компонент с тях. Ако вземем под внимание от родителите на тези приятели и техните приятели, всички тези хора са в една и съща компонент, въпреки че никога не са чували за читателя, говорят на различен език, а до него никога не е било. По този начин, въпреки че световната мрежа на приятелство - не е свързан, читателят ще бъде включен в компонента са много големи, проникваща до всички части на света, която включва хора от най-различни среди и, всъщност, съдържа значителна част от населението на света.

Същото важи и за мрежови комплекти данни - големи, сложни мрежи често имат максимален компонент, който включва значителна част от всички възли. Освен това, когато мрежата съдържа максималния компонент, тя почти винаги е само една. За да разберем защо трябва да се върнем към примера с глобална мрежа на приятелство и да се опитаме да си представим наличието на два максимум компонента, всеки от които включва милиони хора. Това ще изисква наличието на един ръб от един от първите компоненти до втория, така че двата максимални компонента да се слеят в един. Тъй като ръбът е уникален, в повечето случаи е невероятно, че той не се формира и следователно двата максимални компонента в реалните мрежи никога не се наблюдават.

В някои редки случаи, когато двата максимум компонента съжителстват отдавна в истинска мрежа, тяхното обединение беше неочаквано, драматично и в крайна сметка имаше катастрофални последици.

Сливането на компонентите

Например, след пристигането на европейски изследователи в цивилизацията на Западното полукълбо, преди около половин милион години, настъпи глобален катаклизъм. От гледна точка на мрежата изглеждаше така: за пет хиляди години глобалната социална мрежа може би се състоеше от два гигантски компонента - един в Северна и Южна Америка, а другата в Евразия. Поради тази причина се развиха и технологиите, разработени самостоятелно в два компонента, а още по-лошо - човешки заболявания и т.н. Когато двата компонента най-накрая дойдоха в контакт, технологиите и болестите на един бързо и катастрофално запълниха втория.

Американска гимназия

Концепцията за максимални компоненти е полезна за разсъждения за мрежи и в много по-малки размери. Интересен пример е графиката, илюстрираща романтичната връзка в американската гимназия за период от 18 месеца. Фактът, че съдържа максималния компонент, е важно, когато става въпрос за разпространението на болести, предавани по полов път, което е целта на изследването. Учениците може да са имали само един партньор за този период от време, но въпреки това, без да осъзнават това, те са част от максималния компонент и следователно са част от много потенциални пътища за предаване. Тези структури отразяват отношения, които може да са свършили отдавна, но те свързват индивидите във веригите твърде дълго, за да станат обект на голямо внимание и клюки. Въпреки това те са реални: тъй като социалните факти са невидими, но логично течащи макроструктури, които възникват като продукт на индивидуалното посредничество.

Търсене на разстояние и ширина

В допълнение към информацията за това дали две възли са свързани маршрут, теория на графите по компютърни науки дава възможност да се запознаят с неговата дължина - в транспорта, комуникациите и разпространение на новини и заболявания, както и дали тя преминава през няколко върхове или многократно.

За да направите това, определете дължината на маршрута, равна на броя на стъпките, които съдържа от началото до края, т.е. броя на краищата в последователността, която го прави. Например, Масачузетския технологичен институт, BBN, RAND, UCLA маршрут е с дължина 3 и Масачузетския технологичен институт, Юта - 1. С помощта на дължината на пътя, можем да кажем, че ако две възли са разположени в колоната близо един до друг или далеч разстояние между двата върха се определя като дължината на най-краткият път между тях. Например, разстоянието между LINC и SRI е 3, въпреки че за да се уверите в това, трябва да сте сигурни, че няма дължина равна на 1 или 2 между тях.

Алгоритъм за търсене в ширината

За малки графики разстоянието между два възела може лесно да се изчисли. Но за сложните такива съществува необходимост от системен метод за определяне на разстоянията.

Най-естественият начин да направите това и следователно най-ефективният е следният (на примера на глобална мрежа от приятели):

• Всички приятели са обявени за отдалечени от 1.
• Всички приятели на приятели (с изключение на вече маркираните) се обявяват за разположени на разстояние от 2.
• Всичките им приятели (отново, без да броим маркирани хора), се обявяват отдалечени на разстояние от 3.

Продължавайки по този начин, търсенето се извършва в следващите слоеве, всяка от които е една единица отвъд предишната. Всеки нов слой се състои от възли, които все още не са участвали в предишните и които влизат в края с горната част на предишния слой.

Тази техника се нарича търсене с ширина, тъй като тя търси графиката навън от началния възел, като най-напред обхваща най-близките. В допълнение към предоставянето на начин за определяне на разстоянието тя може да послужи като полезна концептуална база за организиране на структурата на графиката, както и как да се изгради графика в информатиката, като се поставят върховете въз основа на тяхното разстояние от определена начална точка.

Търсенето по ширина може да се приложи не само към мрежата от приятели, но и към всяка графика.

Светът е малък

Ако се върнем към глобална мрежа от приятели, можете да видите, че аргументът, който обяснява, принадлежащ към максимална компонент наистина одобрява нещо повече: не само читателят има маршрути до приятели, които да го свързват с една значителна част от населението на света, но тези маршрути са изненадващо кратки ,

Тази идея е наречена "феноменът на близкия свят": светът изглежда малък, ако мислите за това, което кратък маршрут свързва двама души.

Теорията за "шест ръкостискания" първоначално е експериментално изследвана от Стенли Милграм и колегите му през 60-те години. Без да има набор от данни за социални контакти и с бюджет от 680 долара, той реши да провери популярната идея. За тази цел той поиска от 296 случайно избрани инициатори да опитат да изпратят писмо до брокер, който живее в предградие на Бостън. Инициаторите получиха известна лична информация за целта (включително адреса и професията) и трябваше да предадат писмото на лице, което познават по име, със същите инструкции, за да достигне целта възможно най-бързо. Всяко писмо минава през ръцете на няколко приятели и образува верига, която се затваря на борсов посредник извън Бостън.

Сред 64-те вериги, които са достигнали целта, средната дължина е била шест, което се потвърждава от броя, назован преди две десетилетия в заглавието на пиесата от Джон Гари.

Въпреки всички недостатъци на това проучване, експериментът показа един от най-важните аспекти на разбирането ни за социалните мрежи. През следващите години той направи по-широко заключение: социалните мрежи обикновено имат много кратки маршрути между произволни двойки хора. И дори ако тези косвени връзки с бизнес лидери и политически лидери не плащат за себе си на дневна база, наличието на такива кратки маршрути играе голяма роля в скоростта на разпространение на информация, заболявания и други видове инфекции в общността, както и за достъп до възможностите, които социалните мрежи осигурява на хората напълно противоположни качества.