Գրաֆիկները Համակարգչային գիտության: սահմանումը, տեսակները, կիրառման օրինակներ. Գրաֆների տեսություն համակարգչային գիտության

Հաշվում է համակարգչային եղանակով որոշելու համար հարաբերությունները համակցված տարրեր: Սրանք են այն հիմնական օբյեկտներն սովորում են Գրաֆների տեսության.

հիմնական հասկացությունները

Թե ինչ է գրաֆիկի համակարգչային գիտության. Այն իր մեջ ներառում է մի բազմակարծությունը օբյեկտների կոչված հանգույցների կամ գագաթների, որոշ զույգերի, որոնց առնչվում են մ. N. կողիկներ. Օրինակ, գրաֆիկի է գործչի (ա) բաղկացած է չորս հանգույցների, մատնանշում A, B, C եւ D, Բ, որը կապված է յուրաքանչյուր մյուս երեք գագաթների կողոսկրներիդ, եւ C եւ D են նաեւ կապված: Երկու հանգույցների հարեւանությամբ, եթե դրանք կապված են եզրին. Նկարում պատկերված է մի տիպիկ ճանապարհը, թե ինչպես պետք է կառուցել գրաֆիկները համակարգչային գիտության: Շրջանակները ներկայացնում է vertices եւ գծերի կապող յուրաքանչյուր զույգ նրանց, են կողիկներ.

Թե ինչ undirected գրաֆիկի կոչվում է համակարգչային գիտության. Նա հարաբերությունները երկու ծայրերում կողոսկրներիդ են սիմետրիկ: Կող պարզապես կապում նրանց միմյանց հետ: Շատ դեպքերում, սակայն, դա անհրաժեշտ է արտահայտել այն ասիմետրիկ հարաբերությունը, օրինակ, որ A միավոր B, բայց ոչ հակառակը: Այս նպատակն է սահմանումը գրաֆիկի մեջ համակարգչի, դեռեւս բաղկացած է մի շարք հանգույցների հետ մի շարք ուղղված եզրեր: Յուրաքանչյուր կողմնորոշված եզրին է հղում բարձրությունների միջեւ, որոնց ուղղություն ունի իմաստ: Ուղղված գրաֆիկները պատկերել, ինչպես ցույց է տրված նկ (բ), նրանց ծայրերը ներկայացված են Ռադիո. Երբ դուք ուզում եմ շեշտել, որ ոչ-Ուղղորդված գրաֆիկը, այն կոչվում է undirected:

ցանցային մոդելները

Գրաֆիկները համակարգչային գիտության մաթեմատիկական մոդելը ցանցային կառույցների. Հետեւյալ գործիչ ցույց է տալիս, որ կառուցվածքը Ինտերնետում, ապա ծնեց անունը, ARPANET- ին, 1970 թ. Դեկտեմբերին, երբ նա եղել է ընդամենը 13 միավոր: Գործառնական հանգույցներն են վերամշակող կենտրոններ եւ կողիկներ միացնել երկու գագաթներ feedforward therebetween: Եթե դուք չեք ուշադրություն դարձնել, որ Միացյալ Նահանգները պարտադրված քարտեզը, մնացածը պատկերով է 13-հանգույցի գրաֆիկի նման է նախորդ մեկ. Այս դեպքում, փաստացի դիրքորոշում է vertex էական չէ: Դա կարեւոր է, որոնց հանգույցները միացված են միմյանց:

Դիմում գրաֆիկները է համակարգչի թույլ է տալիս տեսնել, թե ինչպես բաներ են կամ ֆիզիկապես, կամ տրամաբանորեն փոխկապակցված է ցանցային կառուցվածքով: 13-հանգույցի ARPANET է մի օրինակ, կապի ցանցի, որը TOP համակարգիչներ կամ այլ սարքերը կարող են փոխանցել հաղորդագրությունները, իսկ եզրերը ներկայացնում ուղղակի հղում, որը տեղեկատվությունը կարող է փոխանցվել:

երթուղիները

Չնայած նրան, որ գրաֆիկները օգտագործվում են տարբեր ոլորտներում, նրանք ունեն ընդհանուր հատկանիշներ: Գրաֆների տեսություն (համակարգչային գիտություն) ներառում թերեւս առավել կարեւոր է նրանց այն գաղափարը, որ ամեն ինչ հաճախ տեղափոխել երկայնքով եզրեր, հերթականությամբ տեղափոխվելուց հանգույցից դեպի հանգույցի, լինի դա ուղեւորը մի քանի չվերթներ կամ տեղեկությունները փոխանցվել մարդուց մարդուն է սոցիալական ցանցում, կամ օգտագործողի համակարգիչ, հետեւողականորեն այցելում է մի շարք վեբ էջերի հետեւելով հղումներ.

Այս գաղափարը դրդում սահմանմանը երթուղին որպես մի շարք հանգույցների կապված է եզրեր: Երբեմն դա անհրաժեշտ է հաշվի առնել այն երթուղին, որը պարունակում է ոչ միայն բաղադրիչներից, այլ նաեւ հաջորդականությունը եզրեր կապող նրանց. Օրինակ, հաջորդականությունը անկյունների MIT- ի, BBN, RAND- ի, UCLA է երթուղին ARPANET ինտերնետային գրաֆիկի: Ընդունումը հանգույցների եւ եզրեր կարող է կրկնվել: Օրինակ, ԳՀԻ, STAN, UCLA, ԳՀԻ, UTAH, MIT է նաեւ երթուղին. Այն ուղին, որի կողիկներ չեն կրկնվում, որը կոչվում է շղթա: Եթե հանգույցները չեն կրկնվում, այն կոչվում է պարզ շղթա:

ցիկլեր

Մասնավորապես կարեւոր տեսակներ համակարգչային գրաֆիկները - այն ցիկլեր որոնք ներկայացնում մատանի կառույց, ինչպիսին է հաջորդականությամբ հանգույցների LiNC, ԴԵՊՔՈՒՄ, CARN, Harv, BBN, Մասաչուսեթսի տեխնոլոգիական ինստիտուտի, LiNC. Երթղինր առնվազն երեք կողերի, որի առաջին եւ վերջին հանգույցը նույնն են, իսկ մնացած տարբեր են, ներկայացնում են մի ցիկլային գրաֆիկները համակարգչային գիտության:

Օրինակներ: SRI ցիկլը, STAN, UCLA, SRI է ամենակարճ, եւ ԳՀԻ, STAN, UCLA, RAND, BBN, UTAH ԳՀԻ զգալիորեն ավելի մեծ է:

Փաստացիորեն ամեն ARPANET- ի բերան գրաֆիկի պատկանում է ցիկլի. Այս ամենն արվել է միտումնավոր, եթե նրանցից որեւէ մեկը չի հաջողվում, կլինի հնարավորությունը անցման մի հանգույցից մյուսը: Ցիկլեր հաղորդակցության եւ տրանսպորտային համակարգերի ներկա են համար ավելորդություն, նրանք ապահովում այլընտրանքային երթուղիների համար մեկ այլ հեծանվային արահետով: Սոցիալական ցանցերը հաճախ են նկատվում ցիկլեր: Երբ եք գտնել, օրինակ, որ մտերիմ դպրոց ընկերը մի զարմիկ ձեր կնոջ, ըստ էության, աշխատում է ձեր եղբոր, դա մի ցիկլ, որը բաղկացած է ձեզանից, ձեր կինը, նրա զարմիկին, նրա ընկեր դպրոցից, իր աշխատողի (այսինքն E. Ձեր եղբայրը), եւ, վերջապես, դու կրկին.

Միացված գրաֆիկի: սահմանումը (համակարգչային գիտություն)

Դա բնական է, պետք է մտածել, թե արդյոք դա հնարավոր է յուրաքանչյուր հանգույց է հասնել ցանկացած այլ հանգույցի: Գրաֆիկը միացված է, եթե կա մի ճանապարհ միջեւ յուրաքանչյուր զույգ vertices: Օրինակ, ARPANET ցանցը միացված գրաֆիկը. Նույնը կարելի է ասել, որ մեծամասնության կապի եւ տրանսպորտային ցանցերի, քանի որ դրանց նպատակն է ուղղել երթեւեկությունը մի հանգույցից մյուսը:

Իսկ մյուս կողմից, չկա մի priori պատճառ է ակնկալել, որ այդ տեսակի գրաֆիկները համակարգչային գիտության համատարած բնույթ են կրում: Օրինակ, սոցիալական ցանցում դժվար չէ պատկերացնել, թե երկու մարդկանց, ովքեր չեն առնչվում միմյանց.

բաղադրիչներ

Եթե սյունակը չի միացված է համակարգչին, բնականաբար, նրանք ընկնում են մի շարք հարակից բեկորները, խմբերի հանգույցների, որը կտրված է եւ չեն հատվում. Օրինակ, նկարը ցույց է երեք այնպիսի հատվածներ: Առաջին - A եւ B, երկրորդը `C, D եւ E, իսկ երրորդը բաղկացած է մնացած vertices:

Բաղադրիչները գրաֆիկի ներկայացնում է մի ենթաբազմություն հանգույցների, որը,

• յուրաքանչյուր vertex ենթախումբ ունի մի ճանապարհ դեպի որեւէ այլ.
• ենթախումբը չէ մասն է ավելի լայն շարք է, որը յուրաքանչյուր հանգույց ունի մի ճանապարհ դեպի որեւէ այլ.

Երբ գրաֆիկները համակարգչի բաժանվում են իրենց բաղադրիչների, դա միայն նախնական մեթոդի նկարագրությունը իրենց կառուցվածքի: Այս բաղադրիչը կարող է լինել հարուստ է ներքին կառուցվածքի, դա կարեւոր է, որ մեկնաբանության ցանցի. Օրինակ, ձեւական մեթոդը որոշելու հանգույցի կարեւորում է որոշելու, թե քանի մասերի է բաժանել հաշվարկը, եթե ուռուցք է հեռացվել:

առավելագույն բաղադրիչը

Կա մի մեթոդ է որակական գնահատման միացումով բաղադրիչների. Օրինակ, կա մի ամբողջ աշխարհում սոցիալական ցանցի կապեր միջեւ երկու մարդ, եթե նրանք ընկերներ.

Արդյոք դա կապված: Հավանաբար ոչ: Միացնելիություն - բավականին փխրուն գույքը, եւ վարքագիծը մեկ հանգույցի (կամ մի փոքր շարք նրանցից) կարող է նվազեցնել այն ոչինչ. Օրինակ, մի անձը, առանց կենդանի ընկերների մի բաղադրիչն բաղկացած մեկ vertex, եւ, հետեւաբար, այդ հաշվարկը չի կապված. Կամ հեռավոր արեւադարձային կղզում, որը բաղկացած է մարդկանց, ովքեր չունեն շփվել արտաքին աշխարհի հետ, կլինի նաեւ մի փոքր բաղադրիչն է ցանցի, որը հաստատում է իր անկապություն.

Համաշխարհային ցանցը ընկերների

Բայց կա մի ուրիշ բան. Օրինակ, մի ընթերցող հայտնի գրքի ունի ընկերներ, ովքեր մեծացել են այլ երկրներում, եւ ստիպում է նրանց մեկ բաղադրիչ: Եթե հաշվի առնենք, որ ծնողներին այդ ընկերների եւ իրենց ընկերների, բոլոր այդ մարդիկ են նաեւ նույն բաղադրիչ, թեեւ նրանք երբեք չէին լսել, որ ընթերցողի, խոսում է այլ լեզվով, եւ հաջորդ դրան երբեք չի եղել: Այսպիսով, չնայած գլոբալ ցանցը բարեկամության կապված չէ, որ ընթերցողը կներառվի բաղադրիչի շատ մեծ է, թափանցել է բոլոր մասերում աշխարհում, որը ներառում է մարդկանց շատ տարբեր ծագմամբ եւ, ըստ էության, պարունակում է մի զգալի մասը աշխարհի բնակչության.

Այդ նույն տեղի է ունենում ցանցային տվյալների սահմանում - մեծ, բարդ ցանցերի հաճախ ունեն առավելագույն բաղադրիչը, որն իր մեջ ներառում է մի զգալի մասն բոլոր հանգույցների. Ավելին, երբ ցանցը ներառում է առավելագույն բաղադրիչ, դա գրեթե միշտ միայն մեկ: Որպեսզի հասկանանք, թե ինչու է, որ անհրաժեշտ է վերադառնալ օրինակով գլոբալ ցանցի բարեկամության եւ փորձում է պատկերացնել գոյությունը երկու, առավելագույնը `բաղադրիչների, որոնցից յուրաքանչյուրը ներառում է միլիոնավոր մարդկանց. Այն պետք է ունենա մի կող մի քանի առաջին բաղադրիչի երկրորդը առավելագույնը երկու բաղադրիչների միացվել են մեկ: Քանի որ միայն մեկ եզրին, շատ դեպքերում դա անհավանական է, որ դա չի ձեւավորվել, եւ հետեւաբար առավելագույնը երկու բաղադրիչներն իրական ցանցերում երբեք չեն նկատվում:

Որոշ հազվագյուտ դեպքերում, երբ երկու բաղադրիչները, որ առավելագույն գոյակցել համար երկար ժամանակ է իրական ցանցում, նրանց միությունը անսպասելի էր, դրամատիկ, եւ, ի վերջո, պետք աղետալի հետեւանքներ:

Դժբախտ պատահար բաղադրիչը միաձուլումը

Օրինակ, ժամանումից հետո եվրոպական Explorers է քաղաքակրթության Արեւմտյան կիսագնդում մոտ կես հազարամյակ առաջ, կար մի գլոբալ արհավիրք: - Ից տեսանկյունից ցանցի, դա նայեցի նման: հինգ հազար տարվա համաշխարհային սոցիալական ցանցի, հավանաբար, բաղկացած երկու հսկա բաղադրիչի մեկը Հյուսիսային եւ Հարավային Ամերիկայում, իսկ մյուսը `Եվրասիայում. Այս պատճառով է, որ տեխնոլոգիան դարձել ինքնուրույն է երկու բաղադրիչների, եւ, նույնիսկ ավելի վատ, քանի որ զարգացած ու մարդկային հիվանդություն, եւ այլն: Դ Երբ երկու բաղադրիչները վերջապես ստացել է սենսորային տեխնոլոգիաների եւ հիվանդության արագ եւ աղետալիորեն վարարումից երկրորդ.

American High School

Հայեցակարգը առավելագույն բաղադրիչի օգտակար է, պատճառաբանելով, մոտ ցանցերի վրա շատ ավելի փոքր մասշտաբով: Հետաքրքիր օրինակ է գրաֆիկի illustrating հարաբերությունները Միացյալ Նահանգների ավագ դպրոցի համար 18-ամսյա ժամանակահատվածում: Այն փաստը, որ այն պարունակում է առավելագույն բաղադրիչը կարեւոր է, երբ խոսքը վերաբերում է տարածման հիվանդությունների, սեռական ճանապարհով փոխանցվող հիվանդությունների, որը հանդիսանում է նպատակը ուսումնասիրության. Ուսանողները կարող են ունեցել ընդամենը մեկ գործընկեր ժամանակ այդ ժամանակահատվածում, բայց, այնուամենայնիվ, առանց գիտակցելու, եղել մի մասը բաղադրիչների առավելագույնը, եւ, հետեւաբար, մի մասը շատ պոտենցիալ երթուղիների փոխանցման: Այս կառույցները արտացոլում հարաբերություններ, որոնք կարող են երկար ժամանակ ավարտվեց, բայց նրանք միացնել մարդկանց չափազանց երկար շղթաներով, լինել առարկա լարված ուշադրության եւ gossip մասին: Այնուամենայնիվ, նրանք իրական են, թե ինչպես են սոցիալական փաստեր են անտեսանելի, բայց հետեւանքային macrostructures առաջացել է որպես ապրանքի անհատական միջնորդության:

Հեռավորությունը եւ լայնութեամբ առաջին որոնում

Ի լրումն տեղեկատվության մասին, թե արդյոք երկու հանգույցների կապված են երթուղին, գրաֆների տեսություն համակարգչային գիտության թույլ է տալիս Ձեզ է իմանալ, իր երկարությամբ, տրանսպորտային, հաղորդակցության կամ տարածման նորությունների եւ հիվանդությունների, ինչպես նաեւ, թե արդյոք այն անցնում է մի քանի գագաթները կամ բազմակի:

Որպեսզի դա անել, սահմանել երթուղու երկարությունը հավասար է թվով քայլերի, որ այն պարունակում է սկզբից մինչեւ վերջ, այսինքն E. թիվն ծայրերը հաջորդականությամբ, որը. Օրինակ, MIT, BBN, RAND, UCLA երթուղին ունի երկարությունը 3, եւ MIT- ի, UTAH 1. Օգտագործելով երկարությունը ճանապարհին, մենք կարող ենք ասել, որ եթե երկու հանգույցների կազմակերպվում են սյունակում մոտ են իրար, կամ հեռու միջեւ հեռավորությունը երկու գագաթները, որը սահմանվում է որպես երկարությամբ ամենակարճ ուղին նրանց միջեւ: Օրինակ, միջեւ հեռավորությունը LiNC եւ ԳՀԻ է 3, թեեւ, պետք է ապահովել, որ այս, դա անհրաժեշտ է ստուգել բացակայությունը երկարությամբ հավասար է 1-ին կամ 2 therebetween.

Breadth առաջին որոնման ալգորիթմը

Փոքր գրաֆիկի միջեւ հեռավորությունը երկու հանգույցների հաշվարկել հեշտությամբ. Բայց դրա համար համալիր կա անհրաժեշտություն է համակարգված եղանակով որոշման հեռավորությունների.

Առավել բնական միջոց է դա անել, եւ, հետեւաբար, առավել արդյունավետ է հետեւյալը (օրինակ, համաշխարհային ցանցը ընկերներին):

• Բոլոր ընկերները հայտարարել են գտնվում է հեռավորության վրա 1:
• Բոլոր ընկերները ընկերների (չհաշված արդեն հիշատակված), որոնք հայտարարել են հեռավորության վրա 2:
• Բոլոր նրանց ընկերները (կրկին, չհաշված պիտակավորված ժողովրդին) հայտարարել է, հեռավոր տարածությունից 3:

Շարունակելով այս ճանապարհով, որ որոնման իրականացվում է հետագա շերտերի, որոնցից յուրաքանչյուրը վրա միավորի վրա նախորդ մեկ. Յուրաքանչյուր նոր շերտը կազմված է հանգույցների, որոնք չեն մասնակցել նախորդներից, եւ որ ընկնում եզրին է vertex է նախորդ շերտի:

Այս տեխնիկան կոչվում է լայնութիւնը առաջին որոնումը, քանի որ նա փնտրում է սյունակի դուրս նախնական հանգույցի, առաջին հերթին ընդգրկելով հաջորդ. Ի լրումն ապահովելով մեթոդը որոշելու հեռավորությունների, ապա դա կարող է ծառայել որպես օգտակար կոնցեպտուալ շրջանակներում կազմակերպելու գրաֆիկի կառուցվածքը, ինչպես նաեւ, թե ինչպես պետք է կառուցել մի գրաֆիկը համակարգչի, ունենալով փիքեր հիման վրա իրենց հեռավորության ֆիքսված ելակետ:

Breadth առաջին որոնումը կարող է կիրառվել ոչ միայն ցանցի ընկերների, այլեւ ցանկացած գրաֆիկի:

փոքր աշխարհը

Եթե դուք գնում եք դեպի մի գլոբալ ցանցի ընկերների, դուք կարող եք տեսնել, որ այն փաստարկը, որ բացատրում պատկանող առավելագույն բաղադրիչի իսկապես հավանում է ավելի շատ բան են ոչ միայն ընթերցողը ունի երթուղիների ընկերների, կապելով նրան զգալի մասը աշխարհի բնակչության, սակայն այդ երթուղիները զարմանալիորեն կարճ ,

Այս գաղափարը, որը կոչվում է «փոքր աշխարհը երեւույթ»: աշխարհը կարծես փոքր, եթե դուք մտածում այդ մասին, թե ինչ է կարճ երթուղի կապում ցանկացած երկու մարդ.

Տեսությունը «վեց handshakes» առաջին անգամ փորձնականորեն հետազոտվել է Սթենլի Միլգրամը եւ նրա գործընկերների հետ 1960-ական թվականներին: Առանց որեւէ շարք սոցիալական ցանցի տվյալների, եւ բյուջեով $ 680, նա որոշել է ստուգել դուրս հայտնի միտքը. Այս նպատակով, նա հարցրեց 296 պատահականորեն ընտրված նախաձեռնողները փորձում են նամակ ուղարկել է բորսային միջնորդ, ով ապրում է մի արվարձան Բոստոնում: Նախաձեռնողները են տվել անձնական տեղեկություններ նպատակների մասին (այդ թվում `հասցեն եւ մասնագիտության), եւ նրանք ստիպված են նամակ ուղարկել այն անձին, ում նրանք գիտեին ըստ անվան հետ նույն հրահանգների, այնպես, որ այն հասել է նպատակին, ինչպես արագ, որքան հնարավոր է. Յուրաքանչյուր նամակ անցել ձեռքում մի շարք ընկերների եւ ձեւավորված մի շղթա փակում է ֆոնդային բրոքերների դուրս Բոստոնում:

Թվում 64 շղթաներով, որոնք հասել է նպատակակետին, միջին երկարությունը եղել է վեց հաստատող թիվը named երկու տասնամյակների վաղ փլեյ Dzhona Gera վերնագրում.

Չնայած բոլոր թերություններին, այս ուսումնասիրության, որ փորձ ցույց տվեց, մեկը կարեւորագույն ասպեկտների մեր հասկացողության սոցիալական ցանցերում: Այն տարիներին, որոնք բխում դա արվել ավելի լայն եզրակացություն: սոցիալական ցանցերը սովորաբար շատ կարճ երթուղիների միջեւ կամայական զույգ մարդկանց. Եւ նույնիսկ, եթե նման անուղղակի կապեր բիզնես առաջնորդների եւ քաղաքական առաջնորդների չեն վճարում իրենց համար է օրական կտրվածքով, ապա գոյությունը նման կարճ երթուղիների խաղում մեծ դեր է արագությամբ տեղեկատվության տարածման, հիվանդության եւ այլ տեսակի վարակի համայնքի, ինչպես նաեւ մուտքի հնարավորությունները, որ սոցիալական ցանցն ապահովում է մարդկանց լրիվ հակառակն է որակները: