Графикони у компјутерске науке: дефиниција, врсте, примери примене. Теорија графова у рачунарству

Тачке методе рачунарског за утврдјивање односа се комбинују елементи. Ово су основни предмет истраживања у теорији графова.

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

Оно што је на графикону у информатике? То укључује мноштво објекте назване чворова или темена, неки парови од којих су повезаних м Н.. ребра. На пример, графикон на слици (а) се састоји од четири чворова, означава А, Б, Ц, и Д, чија Б је повезан са сваким другим три теменима ребра, а Ц и Д су такође повезани. Два чвора су блиски ако су повезани са ивице. На слици је приказан типичан начин како да се изгради графика компјутерских наука. Кругови представљају темена и линије које повезују сваки пар њих су ребра.

Шта ундирецтед графикон се назива у компјутерској науци? Он односи између два краја ребара су симетричне. Ребро их једноставно повезује међусобно. У многим случајевима, међутим, неопходно је да изрази асиметричног односа - на пример, да указује на Б, али не и обрнуто. Овај циљ је дефиниција графикона у компјутеру, и даље састоји од скупа чворова са скупом усмерених ивица. Сваки оријентисана ивица је веза између чворова чији правац има значење. Усмерени графикони приказују, као што је приказано на слици (Б), њихове ивице су представљене стрелицама. Када желите да нагласи да не смера график, то се зове ундирецтед.

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

Графикони у компјутерске науке су математички модел мрежних структура. На следећој слици је приказана структура Интернета, а затим је носио име АРПАНЕТ, у децембру 1970, када је имала само 13 поена. Чворови обрађују центри и ребра повезати два темена феедфорвард између њих. Ако не обраћају пажњу на САД наметнула мапу, остатак слике је 13-чвор граф сличан као у претходном. У том случају, стварни положај врха није од суштинског значаја. Важно је које чворови су међусобно повезани.

Примена графикона у рачунару омогућава да се види како су ствари физички или логички повезани у структури мреже. 13-чвор АРПАНЕТ је пример комуникационе мреже у којој топ рачунари или други уређаји могу да преносе поруке, а ивице представљају директну везу на које информације могу се преносити.

руте

Иако су графикони се користе у многим различитим областима, они имају заједничке карактеристике. Теорија графова (Цомпутер Сциенце) обухвата можда и најважније од њих - идеја да се ствари често крећу дуж ивица, редом креће од чвора до чвора, било да је путник неколико летова или информације преносе са особе на особу у друштвеној мрежи, или корисник рачунар, доследно посети велики број веб страница пратећи везе.

Ова идеја мотивише дефиницију трасе као низ чворова повезаних ивицама. Понекад је потребно узети у обзир пут који садржи не само компоненте, али и низ ивица их повезује. На пример, секвенца чворова МИТ, ББН, РАНД, УЦЛА је пут у АРПАНЕТ интернет графикону. Пролаз чворова и ивица може да се понови. На пример, СРИ, СТАН, УЦЛА, СРИ, УТАХ, МИТ је такође пут. Начин на који се ребра се не понавља, који се зове ланац. Ако се не понавља чворови, то се зове једноставно ланац.

циклуса

Нарочито важни врста компјутерских графиконима - ит циклуси који представљају структуру прстена, као што је секвенца чворова ЛИНЦ, ЦАСЕ, Царн, Харв, ББН, МИТ, ЛИНЦ. Руте са најмање три ребра, у којем је први и последњи чвор су исти, а остатак су различити, представљају цикличне графика компјутерских наука.

Примери: СРИ циклус, СТАН, УЦЛА, СРИ је најкраћа, а СРИ, СТАН, УЦЛА, РАНД, ББН, УТАХ, СРИ знатно већа.

Готово сваки АРПАНЕТ ивицу графикона припада циклусу. То је учињено намерно, ако неко од њих не, да ли ће могућност преласка из једног чвора на други. Циклуси у комуникацијама и транспортним системима су присутни редундантности - пружају алтернативне правце за другом правцу циклуса. На друштвеним мрежама често уочљиви циклуса. Када пронађете, на пример, да је близак школски пријатељ рођака своје жене заправо ради са својим братом, то је циклус који се састоји од вас, ваша жена, њена рођака, његов пријатељ из школе, његов запослених (нпр. Е. Ваш брат), и на крају се опет.

Цоннецтед грапх: дефинитион (цомпутер сциенце)

То је природно да се запитамо да ли је могуће од сваке чвор да се на било који други чвор. Граф је повезан ако постоји пут између сваког пара чворова. На пример, АРПАНЕТ мрежа - повезана граф. Исто се може рећи и за већину комуникационих и транспортних мрежа, као и њихова сврха је да усмери саобраћај из једног чвора на други.

С друге стране, не постоји а приори разлог да се очекује да ова врста графикона у компјутерских наука су широко распрострањени. На пример, у друштвеној мрежи није тешко замислити двоје људи који се не односе једни према другима.

компоненте

Ако колона није повезан са рачунаром, оне природно спадају у сет повезаних фрагмената, групе чворова који су изоловани и не пресецају. На пример, слика приказује три таква дела: Први - А и Б, други - Ц, Д и Е, а трећи чине преосталих темена.

Компоненте графа представљају подскуп чворова, у којој:

• свака вертек подгрупа има пут до било које друге;
• подскуп није део већег скупа у којем сваки чвор има пут до било ког другог.

Када се графикона у компјутеру подељени у својим компонентама, то је само почетна опис метода њихове структуре. Ова компонента може бити богат у унутрашњој структури, важно је за тумачење мреже. На пример, формално метод утврђивања важности чвора је да се утврди колико делова ће бити подељена бројање, ако је чвор је уклоњена.

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

Постоји метода за квалитативну процену за повезивање компоненти. На пример, постоји у свету друштвена мрежа са везама између двоје људи, ако су пријатељи.

Да ли је то повезано? Вероватно не. Повезивање - прилично крхка имовине, а понашање једног чвора (или мали скуп њих) могу да смање ништа. На пример, једна особа без живе пријатељима је компонента која се састоји од једног темена, и према томе, датотека неће бити повезани. Или даљински тропско острво, који се састоји од људи који немају контакт са спољним светом, такође ће бити мали саставни део мреже, што потврђује његову неповезаност.

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

Али постоји нешто друго. На пример, читалац популарне књиге има пријатеље који су одрасли у другим земљама, и чини их једну компоненту. Ако узмемо у обзир родитеље ових пријатеља и њихових пријатеља, сви ови људи су у истој компоненти, иако они никада нису чули за читаоца, говоре други језик, а поред њега никада није било. Тако, иако је глобална мрежа пријатељства - није повезан, читалац ће бити укључени у компоненту су веома велике, продире у све делове света, што укључује људе из различитих средина и, у ствари, садржи значајан део светске популације.

Исто се дешава у сетовима података мреже - велики, сложене мреже често имају максималну компоненту, која укључује значајан део свих чворова. Осим тога, када мрежа садржи максимално компоненту, да је скоро увек само један. Да бисмо разумели зашто, неопходно је да се врати на пример глобалне мреже пријатељства и покушајте да замислите постојање две максималне компоненте, од којих је свака обухвата милионе људи. Она мора да има једну ребро на неки од прве компоненте до другог на максимално две компоненте спојене у једну. Пошто је само један ивице, у већини случајева је невероватно да није формирана, а самим тим и максимално две компоненте у реалним мрежама никада се посматрају.

У неким ретким случајевима, када су две компоненте максимални ко-постоји већ дуже време у правом мрежи, њихова заједница је била неочекивана, драматична, и, на крају, има катастрофалне последице.

Аццидент компонента спајање

На пример, после доласка европских истраживача у цивилизације западне хемисфере око пола миленијума пре, било је глобална катаклизма. Са тачке гледишта мреже, изгледало је овако: пет хиљада година глобалне друштвене мреже, вероватно се састоји од два гиганта компоненте - један у Северној и Јужној Америци, а други - у Евроазији. Из тог разлога, ова технологија је Д. самостално развио у две компоненте, и, што је још горе, као развијена и људске болести, и тако даље. Када су две компоненте коначно добио у технологији тоуцх и болести брзо и катастрофално преплавила други.

Америцан Сцхоол

Концепт максималног компоненте је користан за расуђивање о мрежама на много мањем обиму. Занимљив пример је графикон који приказује однос у средњој школи САД за 18-мјесечног периода. Чињеница да садржи максимално компоненту је од суштинског значаја када је у питању ширење болести, сексуално преносивих болести, која је сврха ове студије. Студенти могу имати само једног партнера у том периоду, али, ипак, не схватајући, су део компоненти максимума, и самим тим, део многих потенцијалних путева преноса. Ове структуре одражава однос који може дуго завршио, али они се повезују појединце у превише дугих ланаца, да буде предмет интензивног надзора и оговарања. Ипак, они су прави: Како друштвене чињенице су невидљиви, али последичне мацроструцтурес настао као производ индивидуалног посредовања.

Удаљеност и претрага у ширину

Поред информација о томе да ли су два чвора повезана пут, теорија графова у рачунарству вам омогућава да сазна своје дужине - у области саобраћаја, комуникација и ширење вести и болести, као и да ли пролази кроз неколико врхова или мултипле.

Да се то уради, дефинисали дужину маршруте једнак броју корака да садржи од почетка до краја, тј. Е. Број ивица у секвенци која је. На пример, МИТ, ББН, РАНД, УЦЛА роуте има дужину од 3, и МИТ, УТАХ - 1. Користећи дужину путање, можемо рећи да ако два чворови су распоређени у колони близу један другом или даљини између два врха је дефинисан као дужина најкраћи пут између њих. На пример, растојање између ЛИНЦ и СРИ је 3, међутим, како би се осигурало ово неопходно да се провери недостатак дужине једнак 1 или 2, између њих.

Претрага у ширину алгоритам

За мале графа удаљености између два чвора израчунати лако. Али за комплекс постоји потреба за систематски метод одређивања растојања.

Најприроднији начин да се то и, самим тим, најефикаснији је следећи (на пример, глобална мрежа пријатеља):

• Сви пријатељи су проглашени налази на удаљености од 1.
• Сви пријатељи пријатеља (не рачунајући већ поменути) су објављени на удаљености 2.
• Сви њихови пријатељи (опет, не рачунајући означене људе) објавио на даљинском удаљености 3.

Настављајући на овај начин, претрес се врши у наредним слојевима, од којих - на уређају и на претходној. Сваки нови слој се састоји од чворова који нису учествовали у претходних, и да падне предност од темена претходног слоја.

Ова техника се зове претрага у ширину, док је тражи у колони од почетног чвора, пре свега покрива следећи. Поред обезбеђивања метод за одређивање растојања, може послужити као користан концептуални оквир за организовање графикона структуру као и како да се изгради графикон рачунара, са вршним основу њихове удаљености од фиксне полазне тачке.

Претрага у ширину може да се примени не само на мрежу пријатеља, али и на било који графикона.

mali свет

Ако се вратимо на глобалној мрежи пријатеља, можете видети да је аргумент који објашњава припадност у највећој компоненту заиста одобрава нешто више: не само читалац има руте пријатељима, да га повезује са значајним уделом светске популације, али ови путеви су изненађујуће кратка .

Ова идеја се назива "мали светски феномен": свет изгледа мало, ако мислите о томе шта је кратак пут повезује било које две особе.

Теорија о "шест руковања" је први пут експериментално истрагу Станлеи Милграм и његове колеге у 1960. Без икаквог скуп података друштвених мрежа, а са буџетом од $ 680, он је одлучио да проверим популарну идеју. У том смислу, он је тражио 296 насумице одабраних иницијатори покушавају да пошаљу писмо брокера, који је живео у предграђу Бостона. Иницијатори су добили неке личне информације о сврси (укључујући адресу и професији), и они су морали да пошаљу писмо особи коју су знали по имену, са истим инструкцијама, тако да достигне циљ што је брже могуће. Свако слово је прошао кроз руке једног броја пријатеља и формира ланац затвара за берзанских посредника изван Бостона.

Међу 64 ланаца које су постигле циљ, просечна дужина је шест, потврђује број именованих две деценије раније у плаи Дзхона Гера титулу.

Упркос свим недостацима ове студије, експеримент је показао један од најважнијих аспеката нашег разумевања друштвених мрежа. У годинама које су уследиле из њега је направљен шири закључак: друштвене мреже имају веома кратке путеве између произвољних парова људи. Па чак и ако такви индиректни везе са пословним лидерима и политичким лидерима не плаћају за себе свакодневно, постојање таквих кратких путева игра велику улогу у брзини ширења информација, болести и других врста инфекција у заједници, као и приступ могућности које друштвене мреже обезбеђује људе са sasvim супротно квалитети.