Grafiken in kompjûter wittenskip: definysje, typen, applikaasje foarbylden. Graph teory in kompjûter wittenskip

Telt in kompjûter metoade foar it fêststellen fan relaasjes wurde kombinearre eleminten. Dat binne de basis foarwerpen fan stúdzje yn grafyk teory.

basic definysjes

Wat is yn de grafyk yn kompjûter wittenskip? It befettet in mearfâldichheid fan foarwerpen neamd knopen of hoekpunten, guon pearen fan hokker wurde ferbûn troch m. N. ribben. Bygelyks, de grafyk yn de figuer (a) bestiet út fjouwer knopen, oanjūn A, B, C en D, B wêrfan is ferbûn oan elk fan de oare trije hoekpunten ribben, en C en D wurde ek ferbûn. Twa knopen binne grinzjend as se wurde ferbûn troch in râne. De figuer toant in typyske wize fan hoe't te bouwen grafiken yn kompjûter wittenskip. Circles fertsjintwurdigje de hoekpunten en de linen ferbinen elk pear fan harren, binne de ribben.

Wat undirected grafyk wurdt neamd yn kompjûter wittenskip? Hy relaasjes tusken de twa einen fen 'e ribben binne symmetrysk. Rib gewoan ferbynt se mei elkoar. Yn in soad gefallen, lykwols, is it nedich om te uterje it asymmetrysk relaasje - bygelyks, dat A punten te B, mar net oarsom. Dizze doelstelling is de definysje fan de grafyk yn 'e kompjûter, noch altyd bestiet út in set fan knopen mei in set fan rjochte rânen. Elke rjochte râne is de link tusken hoekpunten waans rjochting hat betsjutting. Directed grafiken ferbyldzje, lykas werjûn yn figuer (b), harren rânen wurde fertsjintwurdige troch pylken. As jo wolle beklamje dat net-Directional grafyk, dat hjit undirected.

netwurk models

Grafiken in kompjûter wittenskip binne wiskundige model fan netwurk struktueren. De folgjende figuer toant de struktuer fan it ynternet, dan droegen de namme fan 'e ARPANET, yn desimber 1970, doe't se noch mar 13 punten. De knopen binne ferwurkjen fan kearnen en de ribben ferbine de twa hoekpunten feedforward therebetween. As jo net betelje omtinken oan de Feriene Steaten oplein de kaart, de rest fan de ôfbylding is in 13-node grafyk fergelykber mei de foarige. Yn dit gefal, de feitlike posysje fan it vertex is net essinsjeel. It is wichtich om hokker knopen binne ferbûn mei elkoar.

Tapassing fan grafiken yn de kompjûter makket it mooglik om te sjen hoe't dingen binne of fysyk of logyskerwize inoar ferbûn yn in netwurk struktuur. 13-node ARPANET is in foarbyld fan kommunikaasje netwurk dêr't top kompjûters of oare apparaten kinne stjoert berjochten, en de rânen fertsjintwurdigje direkte keppeling op hokker ynformaasje kin oerdroegen wurde.

rûtes

Hoewol't de grafiken wurde brûkt yn in soad ferskillende gebieten, se hawwe mienskiplike skaaimerken. Graph teory (computer wittenskip) omfiemet faaks de meast wichtige dêrfan - it idee dat dingen faak bewege oan de rânen, sequentially beweecht fan node nei node, wês it passazjier in pear flechten of ynformaasje oerbrocht fan persoan ta persoan yn in sosjaal netwurk, of in brûker kompjûter, konsekwint besykjen in tal websiden troch folgjen de links.

Dit idee motivearret de definysje fan 'e rûte as in rige fan knopen ferbûn troch de rânen. Soms is it nedich om te beskôgje de rûte dy't befettet net allinnich komponinten, mar ek in rige rânen ferbine harren. Bygelyks, de opienfolging fan hoekpunten MIT, BBN, RAND, UCLA is in rûte yn ARPANET ynternet grafyk. Trochgong fan knopen en rânen meie wurde werhelle. Bygelyks, SRI, Stan, UCLA, SRI, Utah, MIT is ek in rûte. De wize wêrop't de ribben wurde net werhelle, neamd in keatling. As de knopen binne net werhelle, it hjit in ienfâldige keten.

cycles

Benammen wichtige soarten yn kompjûter grafiken - It fytst dy't fertsjintwurdigje in ring struktuer, lykas in opienfolging fan knopen Linc, gefal Carn, HARV, BBN, MIT, Linc. Rûtes mei op syn minst trije ribben, wêryn de earste en de lêste knoop binne itselde, en de rest binne oars, fertsjintwurdigje Cyclische grafiken yn kompjûter wittenskip.

Foarbylden: SRI syklus, Stan, UCLA, SRI is de koartste, en SRI, Stan, UCLA, RAND, BBN, Utah, SRI flink grutter.

Hast alle ARPANET râne fan de grafyk heart ta de syklus. Dit waard dien mei sin, as ien fan harren net slagget, sil de mooglikheid fan oergong fan de iene node nei in oare. Cycles yn kommunikaasje en ferfier systemen binne oanwêzich foar ûntslach - dizze oanleverje alternative rûtes foar in oare fytspaad. De sosjale netwurken binne faak te fernimmen fytst. As jo fine, bygelyks, dat in nauwe skoalle freon fan in neef fan dyn frou eins wurket mei dyn broer, it is in syklus, dat bestiet út jimme, dyn frou, har neef, syn freon fan skoalle, syn meiwurker (dws. E. Your broer), en as lêste jim wer.

Ferbûn grafyk: definysje (computer wittenskip)

It is natuerlik te ôffreegje oft it mooglik is fan elk knooppunt te krijen ta in oar knooppunt. De grafyk is ferbûn as der in paad tusken alle pear hoekpunten. Bygelyks, de ARPANET netwurk - ferbûn grafyk. Itselde kin sein wurde oer de mearderheid fan kommunikaasje en ferfier netwurken, lykas harren doel is om direkte ferkear fan de iene node nei in oare.

Oan de oare kant, der is gjin a priori reden om te ferwachtsjen dat dizze soarten fan grafiken in kompjûter wittenskip binne wiidferspraat. Bygelyks, yn it sosjale netwurk is net dreech om te tinken twa minsken dy't binne net besibbe oan elkoar.

komponinten

As de kolom wurdt net ferbûn mei de kompjûter, se fansels falle yn in set fan besibbe fragminten, groepen fan knopen dy't isolearre en net kruse. Bygelyks, figuer toant trije sokke dielen: de earste - A en B, de twade - C, D en E, en de tredde bestiet út de oerbleaune hoekpunten.

Ûnderdielen fan de grafyk fertsjintwurdigje in bepaald berik fan knopen, wêryn't:

• eltse vertex subgroep hat in rûte foar elk oar;
• dielsamling is gjin ûnderdiel fan in gruttere set dêr't elk knooppunt hat in rûte nei elk oar.

Doe't de grafiken in kompjûter binne ferdield yn harren ûnderdielen, it is allinnich de earste beskriuwing fan de metoade fan harren struktuer. Dizze komponint kin ryk yn de ynterne struktuer, is it wichtich foar de ynterpretaasje fan it netwurk. Bygelyks, de formele wize fan it fêststellen fan in knooppunt belang is om te bepalen hoefolle parten sille wurde ferdield greve, of de node wurdt fuorthelle.

maksimum komponint

Der is in metoade foar kwalitative hifking fan Konnektivität komponinten. Bygelyks, der is in wrâldwiid sosjale netwurk mei ferbinings tusken twa minsken, as se binne freonen.

Is it ferbûn? Nei alle gedachten net. FerbiningsName - leaver kwetsbere eigendom, en it gedrach fan ien node (of in lyts set fan harren) kinne ferminderjen it nei neat. Bygelyks, in inkele persoan mei gjin libbene freonen is in ûnderdiel dat bestiet út ien inkeld vertex, en dêrom, de telling sil net ferbûn. Of in ôfstân tropyske eilân, besteande út minsken dy't hawwe gjin kontakt mei de bûtenwrâld, sil ek in lyts ûnderdiel fan it netwurk, dy't befêstiget syn incoherence.

Wrâldwide netwurk fan freonen

Mar der is wat oars. Bygelyks, in lêzer fan it populêre boek hat freonen dy't hawwe groeid yn oare lannen, en makket se ien komponint. As wy rekken mei de âlden fan dy freonen en harren freonen, al dizze minsken binne ek yn 'e selde komponint, hoewol't hja hiene nea heard oer de lêzer, sprekke in oare taal, en njonken dat hat nea west. Sa, hoewol't it wrâldwide netwurk fan freonskip - net ferbûn, de lêzer wurdt meinaam yn de komponint binne hiel grut, ynkringende nei alle dielen fan 'e wrâld, dêr't minsken út in protte ferskillende eftergrûnen en, yn feite, befettet in aardich part fan' e wrâldbefolking.

Itselde komt foar yn it netwurk gegevens sets - grut, kompleks netwurken faak hawwe in maksimale komponint, dy't bestiet út in wichtige part fan alle knopen. Boppedat, doe't it netwurk omfiemet in maksimale komponint, it is hast altyd mar ien. Te begripen wêrom, is it nedich om te gean werom nei it foarbyld fan in wrâldwiid netwurk fan freonskip en besykje fuort te tinken it bestean fan twa maximum komponinten, elk fan dat belûkt miljoenen minsken. It moat om in inkele rib op guon fan 'e earste komponint om it twadde ta maksimaal twa komponinten gearfoege ta ien. Sûnt mar ien râne, yn de measte gefallen is it folle kâns op dat it wie net foarme, en dus maksimaal twa komponinten yn it echt netwurken wurde nea waarnommen.

Yn guon seldsume gefallen, doe't de twa ûnderdielen fan de maksimale co-bestien foar in lange tiid yn in echte netwurk, harren uny wie ûnferwachte, dramatysk, en úteinlik hawwe katastrofale gefolgen.

Accident komponint fúzje

Bygelyks, nei de komst fan de Europeeske ûntdekkingsreizgers yn de beskaving fan it westlik healrûn likernôch in heale millennium lyn, wie der in globale Cataclysm. Ut it eachpunt fan it netwurk, it like derop dat dit: fiif tûzen jier fan globale sosjale netwurk, nei alle gedachten bestie út twa Giant komponint - ien yn Noard en Súd-Amearika, en de oare - yn Euraazje. Om dy reden, de technology hat him ûntwikkele selsstannich yn de twa ûnderdielen, en, noch slimmer, lykas ûntwikkele en minsklik sykte, ensafuorthinne. D. Wannear't de twa komponinten einlings krige yn oanrekking technology en in sykte fluch en disastrously overflowed twadde.

American High School

It konsept fan de maksimale ûnderdiel is brûkber foar ferstân oer netwurken op in folle lytsere skaal. In nijsgjirrich foarbyld is in grafyk de rige relaasje yn in Amerikaanske hege skoalle foar de 18-moanne perioade. It feit dat it befettet de maksimum komponint is essinsjeel as it giet om de fersprieding fan syktes, seksueel oerdraachbere sykten, dat is it doel fan 'e stúdzje. Studinten meie hawwe hie mar ien partner yn dy perioade fan tiid, mar, dochs, sûnder realisearjen is, west hawwe diel fan de ûnderdielen fan it maksimum, en dêrom, in diel fan in protte potinsjele rûtes fan de oerdracht. Dy bouwurken reflektearje in relaasje dy't mooglik hawwe lang einige, mar se ferbine yndividuen yn te lang keatling, ta wêzen it ûnderwerp fan intense scrutiny en rabberij. Lykwols, se binne echte: hoe sosjale feiten binne ûnsichtber, mar gefolchskea macrostructures ûntstie as produkt fan yndividuele mediation.

Ôfstân en breedte-earste sykje

Njonken de ynformaasje oer de fraach oft twa knopen binne oansletten rûte, grafyk teory yn kompjûter wittenskip kinne jo leare oer syn lingte - yn ferfier, kommunikaasje of útdragen fan nijs en sykten, en ek oft it giet fia ferskate piken of mear.

Om dit te bepalen in rûte lingte lyk oan it oantal stappen dat it befettet fan begjin oant ein, dws. E. It oantal rânen fan 'e folchoarder dat is. Bygelyks, MIT, BBN, RAND, UCLA rûte hat in lingte fan 3, en MIT, Utah - 1. Mei help fan de lingte fan it paad, kinne wy sizze dat as twa knopen binne ynrjochte yn 'e kolom tichtby elkoar of fier ôfstân tusken de twa piken wurdt definiearre as de lingte fan de koartste paad tusken harren. Bygelyks, de ôfstân tusken de Linc en SRI is 3, al, om te garandearjen dat, is it nedich om te kontrolearjen it ûntbrekken fan langte lyk oan 1 of 2, therebetween.

Breadth-earste sykje algoritme

Foar lytse graph ôfstân tusken twa knopen berekkenje maklik. Mar foar kompleks der ferlet is fan in systematyske metoade fan fêststellen ôfstannen.

De meast natuerlike manier te dwaan en, dêrom, it meast effektyf is it folgjende (bygelyks, in wrâldwiid netwurk fan freonen):

• Alle freonen binne ferklearre leit op in ôfstân fan 1.
• Alle freonen fan freonen (net meirekkene it al neamd) wurde oankundige op ôfstân 2.
• Al harren freonen (wer, net meirekkene it bestimpele minsken) bekend makke op ôfstân ôfstân 3.

Fierder yn dizze manier, it sykjen wurdt útfierd yn lettere lagen, elk fan dat - op de ienheid op de foarige. Elke nije laach is gearstald út knopen dy't hawwe gjin diel oan 'e foarige lju, en dat falle râne fan de vertex fan de foarige laach.

Dizze technyk hjit in breedte-earst sykje, sa't se siket foar de kolom út 'e earste node, it foarste plak dekke de folgjende. Njonken it bieden fan in metoade foar it fêststellen ôfstannen, dat kin tsjinje as in nuttich konseptuele kader te organisearjen de grafyk struktuer en ek hoe't it bouwen fan in grafyk fan de kompjûter, it hawwen Peaks basearre op harren ôfstân fan in fêst útgongspunt.

Breadth-earste sykje kin tapast wurde net allinnich oan in netwurk fan freonen, mar ek nei eltse grafyk.

Small world

As jo geane werom nei in globale netwurk fan freonen, kinne jo sjen dat it argumint dat ferklearret dy't ta de maksimale komponint echt goedkart wat mear: net allinnich de lêzer hat rûtes nei freonen, keppeljen him mei in wichtige part fan 'e wrâld befolking, mar dizze rûtes binne ferrassend koart .

Dat idee wurdt neamd de "lytse wrâld ferskynsel": de wrâld liket lytse, as jo tinke oer wat in koarte rûte ferbynt alle twa persoanen.

De teory fan "seis handshakes" waard earst bearjendewei ûndersocht troch Stanley Milgram en syn kollega yn 'e jierren 1960. Sûnder hokker set fan sosjale netwurk gegevens, en mei in budzjet fan $ 680, besleat er om te kontrolearjen út in populêr idee. Dêrta, hy frege 296 willekeurich selektearre inisjatyfnimmers besykje te stjoeren fan in brief oan 'e stockbroker, dy't wenne yn in foarstêd fan Boston. Inisjatyfnimmers krigen guon persoanlike ynformaasje oer it doel (ynklusyf adres en berop), en hja moasten stjoere in brief oan 'e persoan dy't se wisten troch namme, mei deselde oanwizingen, sa, dat it berikte it doel sa gau as mooglik. Elke brief hat trochjûn troch de hannen fan in oantal freonen en foarme in keatling slút foar stock Makelers bûten Boston.

Under de 64 keatlingen dy't hawwe berikt de doelgroep, de gemiddelde lingte wie seis, befêstiget it oantal neamd twa desennia earder yn it toanielstik Dzhona Gera titel.

Nettsjinsteande al de tekoartkommingen fan dizze stúdzje, it eksperimint demonstraasje fan ien fan de meast wichtige aspekten fan ús begryp fan de sosjale netwurken. Yn de jierren dy't folgen fan it waard makke bredere konklúzje: sosjale netwurken tend to hawwen hiel koarte rûtes tusken willekeurige pearen fan minsken. En sels as sokke yndirekte ferbinings mei saaklike lieders en politike lieders net betelje foar harsels op deistige basis, it bestean fan sokke koarte rûtes spilet in grutte rol yn de snelheid fan ynformaasje fersprieding, sykte en oare soarten ynfeksje yn de mienskip, en ek tagong de kânsen dy't sosjale netwurken jout minsken mei hiel de tsjinoerstelde kwaliteiten.