Mae graffiau mewn gwyddoniaeth gyfrifiadurol: diffiniad, mathau, enghreifftiau cais. theori graff mewn gwyddoniaeth gyfrifiadurol

Cyfrif mewn dull cyfrifiadurol ar gyfer perthnasau penderfynu yn cael eu cyfuno elfennau. Mae'r rhain yn y gwrthrychau sylfaenol o astudio mewn theori graff.

diffiniadau sylfaenol

Beth sydd yn y graff mewn gwyddoniaeth gyfrifiadurol? Mae'n cynnwys lluosogrwydd o wrthrychau a elwir yn nodau neu fertigau, mae rhai parau o'r rhain yn cael eu cysylltu gan m. N. asennau. Er enghraifft, mae'r graff yn y ffigur (a) yn cynnwys pedwar nodau, a ddynodir A, B, C, a D, B sy'n gysylltiedig â phob un o'r tair asen fertigau eraill, ac C a D yn cael eu cysylltu. Mae dau nodau yn gyfagos os ydynt yn cael eu cysylltu gan ymyl. Mae'r ffigur yn dangos ffordd nodweddiadol o sut i adeiladu graffiau mewn gwyddoniaeth gyfrifiadurol. Cylchoedd cynrychioli'r fertigau a'r llinellau sy'n cysylltu pob pâr ohonynt, yn yr asennau.

Gelwir Pa graff undirected yw mewn gwyddoniaeth gyfrifiadurol? Ef berthynas rhwng y ddau ben y asennau yn gymesur. Rib yn syml yn eu cysylltu â'i gilydd. Mewn llawer o achosion, fodd bynnag, mae angen i fynegi perthynas anghymesur - er enghraifft, bod pwyntiau i B, ond nid vice versa. Mae'r amcan hwn yn y diffiniad o'r graff yn y cyfrifiadur, yn dal yn cynnwys set o nodau gyda set o ymylon cyfarwyddyd. Mae pob ymyl oriented yw'r cyswllt rhwng fertigau y mae eu cyfeiriad yn cael ystyr. graffiau Cyfarwyddwyd darlunio, fel y dangosir yn Ffigur (b), eu ymylon yn cael eu cynrychioli gan saethau. Pan fyddwch am bwysleisio bod graff heb fod yn cyfeiriadol, mae'n cael ei alw'n undirected.

modelau rhwydwaith

Mae graffiau mewn gwyddoniaeth gyfrifiadurol yn fodel mathemategol o strwythurau rhwydwaith. Mae'r ffigur canlynol yn dangos strwythur y Rhyngrwyd, ac yna dwyn enw'r ARPANET, ym mis Rhagfyr 1970, pan oedd dim ond 13 o bwyntiau. Mae'r nodau yn prosesu canolfannau a'r asennau cysylltu'r ddwy fertigau therebetween feedforward. Os nad ydych yn talu sylw i'r Unol Daleithiau a osodwyd y map, gweddill y ddelwedd yn graff 13-nod tebyg i'r un blaenorol. Yn yr achos hwn, nid oedd y sefyllfa wirioneddol y fertig yn hanfodol. Mae'n bwysig y mae nodau yn cael eu cysylltu â'i gilydd.

Cymhwyso graffiau yn y cyfrifiadur yn caniatáu i weld sut mae pethau'n naill ai'n gorfforol neu'n gydgysylltiedig yn rhesymegol mewn strwythur rhwydwaith. ARPANET 13-nod yn enghraifft o rwydwaith cyfathrebu y gall cyfrifiaduron top neu ddyfeisiau eraill trosglwyddo negeseuon, ac mae'r ymylon yn cynrychioli cyswllt uniongyrchol y gall gwybodaeth gael ei throsglwyddo.

llwybrau

Er bod y graffiau yn cael eu defnyddio mewn llawer o wahanol feysydd, mae ganddynt nodweddion cyffredin. damcaniaeth Graff (cyfrifiadureg) yn cynnwys o bosibl y mwyaf pwysig ohonynt - y syniad bod pethau yn aml yn symud ar hyd yr ymylon, mewn dilyniant symud o nod i nod, boed yn deithiwr ychydig o hedfan neu wybodaeth a drosglwyddir o berson i berson mewn rhwydwaith gymdeithasol, neu ddefnyddiwr cyfrifiadur, yn gyson ymweld â nifer o dudalennau gwe drwy ddilyn y dolenni.

Mae hyn yn syniad yn cymell y diffiniad o'r llwybr fel cyfres o nodau cysylltu gan ymylon. Weithiau mae angen ystyried y llwybr sy'n cynnwys nid yn unig yn gydrannau, ond hefyd y dilyniant o ymylon eu cysylltu. Er enghraifft, mae'r dilyniant o fertigau MIT, BBN, RAND, UCLA yn llwybr mewn graff rhyngrwyd ARPANET. Efallai y Passage o nodau ac ymylon yn cael ei ailadrodd. Er enghraifft, SRI, STAN, UCLA, SRI, UTAH, MIT hefyd yn llwybr. Mae'r ffordd y nad yw'r asennau yn cael eu hailadrodd, a elwir cadwyn. Os nad yw'r nodau yn cael eu hailadrodd, fe'i gelwir yn gadwyn syml.

cylchoedd

rhywogaethau arbennig o bwysig mewn graffiau cyfrifiadurol - mae cylchoedd sy'n cynrychioli strwythur cylch, megis dilyniant o nodau LINC, CASE, CARN, HARV, BBN, MIT, LINC. Llwybrau gydag o leiaf tair asen, lle y nôd cyntaf a'r olaf yr un fath, ac mae'r gweddill yn wahanol, yn cynrychioli graffiau cylchol mewn gwyddoniaeth gyfrifiadurol.

Enghreifftiau: cylch SRI, STAN, UCLA, SRI yw'r byrraf, a SRI, STAN, UCLA, RAND, BBN, UTAH, SRI sylweddol fwy.

Mae bron pob ymyl ARPANET y graff yn perthyn i'r cylch. Gwnaed hyn yn fwriadol, os bydd unrhyw un ohonynt yn methu, bydd y posibilrwydd o drosglwyddo o un nod i un arall. Cycles mewn cyfathrebu a systemau cludiant yn bresennol ar gyfer dileu swyddi - maent yn darparu llwybrau amgen ar gyfer llwybr beiciau arall. Mae'r rhwydweithiau cymdeithasol yn aml yn cylchoedd amlwg. Pan fyddwch yn dod o hyd, er enghraifft, bod yn ffrind ysgol yn cau o gefnder eich gwraig mewn gwirionedd yn gweithio gyda dy frawd, mae'n gylch sy'n cynnwys chi, eich gwraig, ei chefnder, ei ffrind o'r ysgol, ei weithiwr (hy. D. Eich brawd), ac yn olaf i chi eto.

graff Connected: Diffiniad (cyfrifiadureg)

Mae'n naturiol meddwl tybed a yw'n bosibl o bob nod i gyrraedd unrhyw nod arall. Mae'r graff yn gysylltiedig os oes llwybr rhwng pob pâr o fertigau. Er enghraifft, mae'r rhwydwaith ARPANET - cysylltu graff. Gellir dweud yr un peth am y rhan fwyaf o rwydweithiau cyfathrebu a thrafnidiaeth, gan fod eu pwrpas yw cyfeirio traffig o un nod i un arall.

Ar y llaw arall, nid oes rheswm i ddisgwyl priori bod y mathau hyn o graffiau mewn gwyddoniaeth gyfrifiadurol yn gyffredin. Er enghraifft, yn y rhwydwaith cymdeithasol ddim yn anodd dychmygu dau o bobl nad ydynt yn perthyn i'w gilydd.

cydrannau

Os na fydd y golofn yn cael ei gysylltu â'r cyfrifiadur, maent yn naturiol yn perthyn i set o ddarnau cysylltiedig, grwpiau o nodau sy'n cael eu hynysu ac nid ydynt yn croestorri. Er enghraifft, Ffigur yn dangos tair rhan o'r fath: y cyntaf - A a B, yr ail - C, D ac E, ac mae'r trydydd yn cynnwys y fertigau weddill.

Cydrannau y graff yn cynrychioli is-set o nodau, lle:

• mae gan bob is-grŵp fertig llwybr i unrhyw un arall;
• Nid yw is-set yn rhan o set fwy lle mae pob nod yn cael llwybr i unrhyw un arall.

Pan fydd y graffiau mewn cyfrifiadur yn cael eu rhannu i mewn i'w cydrannau, dim ond y disgrifiad cyntaf o'r dull eu strwythur. Gall hyn gydran fod yn gyfoethog yn y strwythur mewnol, mae'n bwysig i ddehongli'r rhwydwaith. Er enghraifft, y dull ffurfiol o benderfynu ar bwysigrwydd nod yw pennu faint o rannau fydd yn cael ei rannu cyfrif, os mae 'r nôd yn cael ei symud.

cydran uchafswm

Mae dull ar gyfer asesiad ansoddol o gydrannau cysylltedd. Er enghraifft, mae rhwydwaith cymdeithasol byd-eang gyda chysylltiadau rhwng dau o bobl, os ydynt yn ffrindiau.

A yw'n gysylltiedig? Mae'n debyg nad yw. Cysylltedd - Gall eiddo yn hytrach fregus, ac ymddygiad un nôd (neu set fach ohonynt) ei leihau i ddim. Er enghraifft, mae person sengl heb unrhyw ffrindiau sy'n byw yn elfen sy'n cynnwys fertig sengl, ac felly, ni fydd y cyfrif yn cael ei gysylltu. Neu ynys drofannol anghysbell, sy'n cynnwys pobl sydd heb unrhyw gysylltiad â'r byd y tu allan, hefyd yn elfen fach o'r rhwydwaith, sy'n cadarnhau ei ddiffyg cyswllt.

rhwydwaith byd-eang o ffrindiau

Ond mae rhywbeth arall. Er enghraifft, mae darllen y llyfr poblogaidd gan ffrindiau sydd wedi tyfu i fyny mewn gwledydd eraill, ac yn eu gwneud yn un gydran. Os byddwn yn cymryd i ystyriaeth y rhieni o ffrindiau hyn a'u cyfeillion, holl bobl hyn hefyd yn yr un gydran, er nad oeddent erioed wedi clywed am y darllenydd, yn siarad iaith wahanol, ac yn nesaf iddo erioed wedi bod. Felly, er bod y rhwydwaith byd-eang o gyfeillgarwch - nad ydynt yn gysylltiedig, y darllenydd yn cael ei gynnwys yn y gydran yn fawr iawn, treiddio i bob rhan o'r byd, sy'n cynnwys pobl o nifer o wahanol gefndiroedd ac, mewn gwirionedd, yn cynnwys cyfran sylweddol o boblogaeth y byd.

Ceir yr un fath yn y setiau data rhwydwaith - rhwydweithiau mawr, cymhleth yn aml yn cael cydran mwyaf, sy'n cynnwys cyfran sylweddol o'r holl nodau. Ar ben hynny, pan fydd y rhwydwaith yn cynnwys elfen uchaf, mae bron bob amser yn un yn unig. Er mwyn deall pam, mae angen mynd yn ôl at yr enghraifft o rwydwaith byd-eang o gyfeillgarwch ac yn ceisio dychmygu bodolaeth dwy elfen y mwyaf, pob un ohonynt yn cynnwys miliynau o bobl. Mae angen iddo gael asen unigol ar rai o'r elfen gyntaf i'r ail at uchafswm ddwy gydran cyfuno i mewn i un. Gan un ymyl yn unig, yn y rhan fwyaf o achosion, mae'n annhebygol nad ei ffurfio, ac felly byth uchafswm dwy elfen mewn rhwydweithiau go iawn yn cael eu dilyn.

Mewn rhai achosion prin, pan fydd y ddwy elfen o'r uchafswm cyd-bodoli ers amser maith mewn rhwydwaith go iawn, eu hundeb yn annisgwyl, dramatig, ac, yn y pen draw, arwain at ganlyniadau trychinebus.

uno gydran Damweiniau

Er enghraifft, ar ôl dyfodiad fforwyr Ewropeaidd yn y gwareiddiad y Gorllewin Hemisffer tua hanner mileniwm yn ôl, roedd cataclysm byd-eang. O safbwynt y rhwydwaith, roedd yn edrych fel hyn: bum mil o flynyddoedd o rwydwaith cymdeithasol byd-eang, yn ôl pob tebyg yn cynnwys dau gydran mawr - un yng Ngogledd a De America, ac yn y llall - yn Ewrasia. Am y rheswm hwn, mae'r dechnoleg wedi esblygu yn annibynnol yn y ddwy gydran, a, hyd yn oed yn waeth, fel y datblygwyd ac afiechydon dynol, ac yn y blaen. D. Pan fydd y ddwy elfen o'r diwedd mewn technoleg cyffwrdd a chlefyd yn gyflym ac yn drychinebus yn gorlifo yn ail.

Ysgol Uwchradd Americanaidd

Mae'r cysyniad o gydran uchaf yn ddefnyddiol ar gyfer rhesymu am rwydweithiau ar raddfa llawer llai. Enghraifft ddiddorol yw graff sy'n dangos y berthynas mewn ysgol uwchradd Unol Daleithiau ar gyfer y cyfnod o 18 mis. Mae'r ffaith ei fod yn cynnwys yr elfen uchaf yn hanfodol pan ddaw i lledaeniad clefydau, clefydau a drosglwyddir yn rhywiol, sef diben yr astudiaeth. Gall myfyrwyr fod wedi dim ond un partner yn ystod y cyfnod hwnnw, ond, serch hynny, heb sylweddoli hynny, wedi bod yn rhan o elfennau o'r uchafswm, ac felly, yn rhan o nifer o lwybrau posibl o drosglwyddo. Mae'r strwythurau hyn yn adlewyrchu'r berthynas a allai fod wedi dod i ben hir, ond maent yn cysylltu unigolion mewn cadwyni yn rhy hir, i fod yn destun craffu dwys a chlecs. Serch hynny, maent yn real: sut ffeithiau cymdeithasol yn anweledig, ond macrostructures-ddilynol i'r amlwg fel cynnyrch o gyfryngu unigol.

Pellter ac ehangder-gyntaf chwiliad

Yn ogystal â'r wybodaeth ynghylch a dau nodau yn cael eu cysylltu llwybr, theori graff mewn gwyddoniaeth gyfrifiadurol yn eich galluogi i ddysgu am ei hyd - mewn trafnidiaeth, cyfathrebu neu lledaenu newyddion a chlefydau, yn ogystal ag a yw'n mynd drwy sawl copa neu luosog.

I wneud hyn, yn diffinio hyd llwybr hafal i nifer o gamau y mae'n ei gynnwys o'r dechrau i'r diwedd, hy. E. Mae nifer yr ymylon yn y dilyniant sy'n cael ei. Er enghraifft, MIT, BBN, RAND, llwybr UCLA mae hyd o 3, a MIT, UTAH - 1. Defnyddio hyd y llwybr, gallwn ddweud bod os oes dau nodau yn cael eu trefnu yn y golofn agos at ei bellter eraill neu bell rhwng y ddau copaon ei ddiffinio fel hyd y y llwybr byrraf rhyngddynt. Er enghraifft, y pellter rhwng y LINC a SRI yw 3, fodd bynnag, er mwyn sicrhau hyn, mae angen i wirio absenoldeb o'r un hyd at 1 neu 2, therebetween.

algorithm chwilio Ehangder-gyntaf

Ar gyfer pellter graff bach rhwng dau nodau cyfrifo yn hawdd. Ond ar gyfer gymhleth, mae angen am ddull systematig o benderfynu ar bellteroedd.

Y ffordd fwyaf naturiol o wneud hyn ac, felly, y mwyaf effeithiol yw'r canlynol (er enghraifft, rhwydwaith byd-eang o ffrindiau):

• Mae'r holl ffrindiau yn datgan lleoli ar bellter o 1.
• Mae pob ffrindiau o ffrindiau (heb gyfrif y soniwyd amdanynt eisoes) yn cael eu cyhoeddi yn bellter 2.
• Mae eu holl ffrindiau (eto, heb gyfrif y bobl labelu) cyhoeddi ar bellter o bell 3.

Parhau yn y modd hwn, mae'r chwilio yn cael ei wneud mewn haenau dilynol, pob un ohonynt - ar yr uned ar yr un blaenorol. Mae pob haen newydd yn cynnwys nodau nad ydynt wedi cymryd rhan yn y rhai blaenorol, ac sy'n disgyn ymyl o fertig yr haen blaenorol.

Gelwir y dechneg hon chwiliad ehangder-cyntaf, wrth iddi chwilio am y golofn allan y nôd gwreiddiol, yn bennaf am y nesaf. Yn ogystal â darparu dull o bennu pellteroedd, gall gyflwyno fel fframwaith cysyniadol defnyddiol i drefnu strwythur y graff yn ogystal â sut i adeiladu graff o gyfrifiadur, cael copa yn seiliedig ar eu pellter o fan cychwyn penodol.

Gall chwilio Ehangder-cyntaf yn cael eu cymhwyso nid yn unig i rwydwaith o ffrindiau, ond hefyd i unrhyw graff.

byd bach

Os byddwch yn mynd yn ôl i rwydwaith byd-eang o ffrindiau, gallwch weld bod y ddadl bod yn egluro perthyn i'r gydran uchafswm wir yn cymeradwyo rhywbeth mwy: Mae gan nid yn unig y darllenydd llwybrau at ffrindiau, gan gysylltu ag ef gyda chyfran sylweddol o boblogaeth y byd, ond mae llwybrau hyn yn rhyfeddol o fyr .

Gelwir y syniad yw y "ffenomenon byd bach": y byd yn ymddangos yn fach, os ydych yn meddwl am yr hyn y llwybr byr yn cysylltu unrhyw ddau o bobl.

Mae'r ddamcaniaeth o "chwe ysgwyd llaw" ei gyntaf ymchwilio arbrofol gan Stanley Milgram a'i gydweithwyr yn y 1960au. Heb gael unrhyw set o ddata rhwydwaith cymdeithasol, a chyda chyllideb o $ 680, penderfynodd atalfa i maes yn syniad poblogaidd. I'r perwyl hwn, gofynnodd 296 cychwynwyr dewis ar hap ceisio anfon llythyr at y brocer stoc, a oedd yn byw mewn maestref o Boston. Cychwynwyr Rhoddwyd rhywfaint o wybodaeth bersonol am bwrpas (gan gynnwys cyfeiriad a phroffesiwn), ac roedd yn rhaid iddynt anfon llythyr at y person y maent yn gwybod yn ôl enw, gyda'r un cyfarwyddiadau, fel ei fod yn cyrraedd y nod cyn gynted ag y bo modd. Mae pob llythyr wedi pasio drwy ddwylo nifer o ffrindiau a ffurfio cadwyn yn cau am broceriaid stoc y tu allan i Boston.

Ymhlith y 64 o cadwynau sydd wedi cyrraedd y targed, hyd cyfartalog oedd chwech, cadarnhau nifer yr enwir dau ddegawd yn gynharach yn y ddrama teitl Dzhona Gera.

Er gwaethaf yr holl ddiffygion yr astudiaeth hon, yr arbrawf Dangosodd un o'r agweddau pwysicaf ar ein dealltwriaeth o'r rhwydweithiau cymdeithasol. Yn y blynyddoedd dilynol ohono gael ei wneud casgliad ehangach: rhwydweithiau cymdeithasol yn tueddu i fod llwybrau byr iawn rhwng parau mympwyol o bobl. A hyd yn oed os nad yw cysylltiadau o'r fath anuniongyrchol gydag arweinwyr busnes ac arweinwyr gwleidyddol yn talu am eu hunain yn ddyddiol, mae bodolaeth llwybrau byr o'r fath yn chwarae rhan fawr yn y cyflymder y lledaenu gwybodaeth, clefyd a mathau eraill o haint yn y gymuned, yn ogystal â mynediad y cyfleoedd a rhwydweithio cymdeithasol yn rhoi pobl sydd â eithaf nodweddion gyferbyn.