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

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

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

Она што е во графиконот во компјутерски науки? Тоа вклучува множество на објекти наречени јазли или темиња, некои парови кои се поврзани со м. Н. ребра. На пример, на графикот на сликата (а) се состои од четири јазли, означена A, B, C и D, B на кој е поврзан со секоја од другите три темиња ребра, и C и D, исто така, се поврзани. Два јазли се во непосредна близина, ако тие се поврзани со раб. Бројката покажува типичен начин за тоа како да се изгради графикони во компјутерската наука. Circles претставуваат темиња и линии за поврзување секој пар од нив, се ребрата.

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

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

Графици во компјутерски науки се математички модел на мрежни структури. На следната слика е прикажана структурата на интернет, тогаш го носеше името на ARPANET, во декември 1970 година, кога имала само 13 поени. Јазли се обработка центри и ребрата се поврзете на две темиња feedforward помеѓу нив. Ако не се обрне внимание на САД наметнати на мапата, а остатокот на сликата е 13-графикон јазол сличен на претходниот. Во овој случај, на вистинската позиција на теме не е од суштинско значење. Тоа е важно да се што јазли се поврзани едни со други.

Примена на графикони во компјутер им овозможува да се види како работите се или физички или логички меѓусебно се поврзани во мрежа структура. 13-јазол ARPANET е пример на комуникациска мрежа во која врвни компјутери или други уреди можат да пренесуваат пораки, и на рабовите претставуваат директна врска на кои информации може да се пренесе.

правци

Иако графикони се користи во многу различни области, тие имаат заеднички карактеристики. Графикон теорија (компјутерски науки) вклучува можеби најважниот од нив - на идејата дека работите често се движат по должината на рабовите, последователно се движат од јазол да јазол, било да е тоа патнички неколку летови или информации кои се пренесуваат од човек на човек во социјална мрежа, или корисник компјутер, постојано во посета на голем број на веб страни од следниве линкови.

Оваа идеја мотивира дефиницијата на пат како серија на јазли поврзани со рабови. Понекогаш е потребно да се разгледа на пат кој не содржи само компоненти, но, исто така, редоследот на рабовите поврзувајќи ги. На пример, низата од темиња МИТ, BBN, Ранд, Лос Анџелес е пат во ARPANET интернет графиконот. Усвојувањето на јазли и рабовите може да се повтори. На пример, СРИ, Стен, Лос Анџелес, СРИ, Јута, МИТ е исто така еден пат. Начинот на кој ребра не се повторуваат, се нарекува синџир. Ако јазли не се повторува, тоа се нарекува едноставно синџир.

циклуси

Особено значајни видови во компјутерски графикони - тоа циклуси кои претставуваат прстенеста структура, како што се низа на јазли ЛИНК, случај, Carn, Harv, BBN, МИТ, ЛИНК. Патишта со најмалку три ребра, во која првата и последната јазол се исти, а остатокот се различни, претставуваат циклична графикони во компјутерската наука.

Примери: СРИ циклус, STAN, Лос Анџелес, СРИ е најкраткиот и СРИ, Стен, Лос Анџелес, РАНД, BBN, Јута, Шри значително поголема.

Буквално секој ARPANET работ на графиконот припаѓа на циклусот. Ова беше направено намерно, ако некој од нив не успее, ќе можноста за премин од еден јазол до друг. Циклуси во комуникациски и транспортни системи се присутни за технолошки вишок - тие се обезбеди алтернативни правци за друг пат циклус. Социјалните мрежи често се забележува циклуси. Кога ќе се најде, на пример, дека близок другар на роднина на жена ти, всушност, работи со брат ти, тоа е циклус кој се состои од вас, вашата сопруга, нејзината братучетка, неговиот пријател од училиште, неговиот вработен (на пр. Е. Вашиот брат), а на крај повторно.

Поврзан графикон: дефиниција (компјутерски науки)

Тоа е природно да се прашувам дали е можно од секој јазол да се дојде до било кој друг јазол. На графиконот е поврзан ако постои пат помеѓу секој пар на темиња. На пример, мрежата ARPANET - поврзани графиконот. Истото може да се каже и за поголемиот дел од комуникацијата и транспортни мрежи, бидејќи нивната цел е да го насочуваат сообраќајот од еден јазол до друг.

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

компоненти

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

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

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

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

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

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

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

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

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

Истото се случува во сетови на податоци мрежа - големи, сложени мрежи често имаат максимална компонента, која вклучува значителен дел од сите јазли. Покрај тоа, кога мрежата вклучува максимум компонента, тоа е речиси секогаш само еден. За да се разбере зошто тоа, потребно е да се вратиме на примерот на глобалната мрежа на пријателство и да се обиде да се замисли постоењето на две максимум компоненти, од кои секоја вклучува милиони луѓе. Тоа треба да имаат еден ребро на некои од првата компонента на вториот до максимум две компоненти споени во една. Бидејќи само еден раб, во повеќето случаи, тоа е неверојатно дека тоа не е формирана, а со тоа најмногу две компоненти во реалниот мрежи никогаш не се почитуваат.

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

Несреќа спојување компонента

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

Американската гимназија

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

Растојание и ширина и првиот пребарување

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

Да го направите ова, се дефинира должината на трасата е еднаков на бројот на чекори кои што содржи од почеток до крај, односно. Е. Бројот на рабовите во низа што е. На пример, МИТ, BBN, Ранд, Лос Анџелес пат е со должина од 3, и МИТ, Јута - 1. Користење на должината на патеката, можеме да кажеме дека ако два јазли се наредени во колона блиску еден до друг или далеку растојанието помеѓу две врвови се дефинира како должината на најкраткиот пат помеѓу нив. На пример, растојанието помеѓу ЛИНК и СРИ е 3, сепак, да се обезбеди тоа, потребно е да се провери отсуството на должина еднаква на 1 или 2, помеѓу нив.

Ширина и првиот пребарување алгоритам

За мали графиконот растојание помеѓу два јазли се пресмета лесно. Но, за комплексот има потреба за систематски метод на утврдување растојанија.

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

• Сите пријатели се прогласени наоѓа на растојание од 1.
• Сите пријатели на пријатели (не сметајќи на веќе споменатите) се објавени на далечина 2.
• Сите нивни пријатели (повторно, не сметајќи ги етикетирани луѓе) во далечинскиот управувач од далечина 3.

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

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

Ширина и првиот пребарување може да се примени не само на мрежа на пријатели, но, исто така, било графиконот.

мал свет

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

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

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

Меѓу 64 синџири кои постигнале целта, просечната должина шест години, се потврдува бројот на именувани две децении претходно во игра Dzhona Gera титула.

И покрај сите недостатоци на оваа студија, експериментот покажа еден од најважните аспекти на нашето разбирање на социјалните мрежи. Во годините кои следеа од него беше направен поширок заклучок: социјални мрежи имаат тенденција да имаат многу краток правци помеѓу произволна парови на луѓе. И дури и ако таквите индиректни врски со бизнис лидери и политички лидери не плаќаат за себе на дневна основа, постоењето на такви кратки насоки игра голема улога во брзината на ширење на информации, болести и други видови на инфекција во заедницата, како и пристап до можностите кои социјалните мрежи обезбедува на луѓето со сосема спротивното квалитети.