Graif san eolaíocht ríomhaireachta: sainmhíniú, cineálacha, samplaí iarratais. teoiric graf san eolaíocht ríomhaireachta

Comhaireamh i Modh ríomhaireachta do chaidrimh a chinneadh go bhfuil eilimint ann i. Is iad seo na cuspóirí bunúsacha staidéir in teoiric graf.

sainmhínithe bunúsacha

Cad é sa ghraf in eolaíocht ríomhaireachta? Cuimsíonn sé iolrachas na rudaí ar a dtugtar nóid nó rinn, cuid péirí a bhfuil baint ag m. N. easnacha. Mar shampla, Is éard atá an graf san fhigiúr (a) de cheithre nóid, denoted A, B, C, agus D, B ar a bhfuil baint le gach ceann de na trí eile ribs rinn, agus C agus D atá ceangailte freisin. Tá dhá nóid in aice má cheanglaítear iad ag imeall. Taispeánann an fhíor bealach is gnách ar conas graif san eolaíocht ríomhaireachta a thógáil. ionadaíocht a dhéanamh Ciorcail na rinn agus na línte nascadh gach péire acu, is iad na ribs.

Tá Cén graf undirected dtugtar san eolaíocht ríomhaireachta? Tá caidreamh Sé idir an dá foircinn an easnacha siméadrach. Rib nascann ach iad lena chéile. In a lán cásanna, áfach, is gá a chur in iúl ar an gcaidreamh neamhshiméadrach - mar shampla, go bhfuil A pointí go B, ach ní vice versa. Is é an cuspóir seo an míniú ar an ghraf sa ríomhaire, fós comhdhéanta de shraith de nóid le sraith de imill stiúrtha. Tá gach imeall dírithe ar an nasc idir rinn a seoltar tá brí. graif Stiúrtha thaispeáint, mar a thaispeántar i bhFíor (b), a n-imill Tá ionadaíocht ag saigheada. Nuair is mian leat chun béim go graf neamhthreocha, tá sé ar a dtugtar undirected.

samhlacha líonra

Tá Graif san eolaíocht ríomhaireachta samhail mhatamaiticiúil struchtúir líonra. Taispeánann an figiúr seo a leanas struchtúr an Idirlíon, rug ansin an t-ainm an ARPANET, i mí na Nollag 1970, nuair a bhí sí ach 13 pointí. Is iad na nóid hionaid próiseála agus an ribs nascadh an dá rinn feedforward therebetween. Mura bhfuil tú aird a thabhairt ar na Stáit Aontaithe a fhorchuirtear ar an léarscáil, tá an chuid eile den íomhá graf 13-nód cosúil leis an gceann roimhe sin. Sa chás seo, nach bhfuil an staid iarbhír an rinn riachtanach. Tá sé tábhachtach a bhfuil nóid iad ceangailte le chéile.

Ceadaíonn Feidhm graif sa ríomhaire a fheiceáil conas a bhfuil rudaí ceachtar idirnasctha go fisiciúil nó go loighciúil i struchtúr líonra. Is 13-nód ARPANET sampla de líonra cumarsáide inar féidir le ríomhairí barr nó gléasanna eile teachtaireachtaí a tharchur, agus ar na himill ionadaíocht nasc díreach inar féidir soláthar faisnéise a tharchur.

bealaí

Cé go bhfuil na graif a úsáidtear i go leor réimsí éagsúla, tá siad gnéithe comónta. Áirítear teoiric graf (eolaíocht ríomhaireachta) dócha gurb é an ceann is tábhachtaí acu - an smaoineamh go rudaí a bhogadh go minic ar feadh an imill, seicheamhach bogadh ó nód go nód, go mbeadh sé paisinéir cúpla eitiltí nó faisnéis a tharchuirtear ó dhuine go duine sa líonra sóisialta, nó d'úsáideoir ríomhaire, ag tabhairt cuairte go seasta roinnt leathanaigh ghréasáin trí na naisc.

spreagann an smaoineamh an sainmhíniú ar an mbealach mar shraith de nóid ceangailte ag himill. Uaireanta is gá a mheas ar an mbealach go bhfuil nach comhábhair amháin, ach freisin an t-ord na n imill iad a nascadh. Mar shampla, an t-ord na reann MIT, BBN, RAND, tá UCLA bealach ar ghraf idirlín ARPANET. Is féidir Pasáiste na nóid agus imill a athdhéanamh. Mar shampla, Srí, STAN, UCLA, Srí, UTAH, tá MIT chomh maith ar chúrsaí. An bealach ina nach bhfuil an ribs arís agus arís eile, ar a dtugtar slabhra. Mura bhfuil na nóid arís agus arís eile, tá sé ar a dtugtar slabhra simplí.

timthriallta

speiceas A bheith tábhachtach i graif ríomhaireachta - timthriallta sé a léiríonn struchtúr fáinne, ar nós sraith de nóid LINC, CÁS, CARN, Harv, BBN, MIT, LINC. Tá Bealaí a bhfuil ar a laghad trí ribs, ina bhfuil an chéad seo caite nód an gcéanna, agus an chuid eile éagsúla, ionadaíocht a dhéanamh graif ciorclach san eolaíocht ríomhaireachta.

Is timthriall Srí, STAN, UCLA, Srí an giorra, agus Srí, STAN, UCLA, RAND, BBN, UTAH, Srí i bhfad níos mó: Samplaí.

Beagnach mbaineann gach imeall ARPANET an ghraif don timthriall. Rinneadh é sin d'aon ghnó, má theipeann ar aon cheann acu, beidh ar an bhféidearthacht aistriú ó nód amháin go ceann eile. Tá Timthriallta i gcórais iompair chumarsáide agus i láthair le haghaidh iomarcaíochta - a chuireann siad ar bhealaí malartacha chun raon rothaíochta eile. Is iad na líonraí sóisialta go minic timthriallta faoi deara. Nuair a fhaigheann tú, mar shampla, go n-oibríonn cara scoile dlúth le col ceathrar de do bhean chéile i ndáiríre le do dheartháir, tá sé ina timthriall sin comhdhéanta de tú, do bhean chéile, a col ceathrar, a chara ón scoil, a fhostaí (ie. E. Do deartháir), agus ar deireadh tú arís.

graf Nasctha: sainmhíniú (eolaíocht ríomhaireachta)

Tá sé nádúrtha chun Wonder cibé an bhfuil sé indéanta ó gach nód a fháil ar aon nód eile. Is é an graf ceangailte má tá cosán idir gach péire de reanna. Mar shampla, an líonra ARPANET - nasctha graf. Is féidir an rud céanna a rá mar gheall ar an chuid is mó de líonraí cumarsáide agus iompair, mar go bhfuil a n-aidhm tráchta díreach ó nód amháin go ceann eile.

Ar an láimh eile, tá cúis priori a bheith ag súil go bhfuil na cineálacha graif san eolaíocht ríomhaireachta go forleathan nach bhfuil aon. Mar shampla, sa líonra sóisialta nach bhfuil sé deacair a shamhlú beirt daoine nach bhfuil gaol acu lena chéile.

comhpháirteanna

Mura bhfuil an colún ceangailte leis an ríomhaire, tá siad luíonn go nádúrtha i sraith de blúirí gaolmhara, grúpaí nóid atá scoite amach agus nach a chéile. Mar shampla, léiríonn Figiúr thrí chuid den sórt sin: an chéad - A agus B, an dara - C, D agus E, agus an tríú cuid comhdhéanta de na reanna eile.

Comhpháirteanna den ghraf ar son fo-thacar de nóid, ina bhfuil:

• Tá gach foghrúpa rinn bealach ar bith eile;
• Níl an fo-thacar chuid de shraith níos mó ina bhfuil gach nód bealach ar bith eile.

Nuair a bheidh na graif i ríomhaire roinnte ina a gcomhpháirteanna, tá sé ach an cur síos tosaigh ar mhodh a struchtúir. D'fhéadfadh sé seo a chomhdhéanann í a bheith saibhir i struchtúr inmheánach, tá sé tábhachtach maidir le léiriú an ghréasáin. Mar shampla, is é an modh foirmiúil a chinneadh tábhacht nód chun a chinneadh cé mhéad páirt a a roinnt chomhaireamh, má tá an nód a bhaint.

chomhdhéanann í uasmhéid

Tá modh le haghaidh measúnú cáilíochtúil ar chomhpháirteanna nascacht. Mar shampla, tá líonra sóisialta ar fud an domhain le naisc idir dhá daoine, más rud é go bhfuil siad cairde.

Ceangailte air? Is dócha nach bhfuil. Nascacht - Is féidir le maoin in áit leochaileacha, agus iompar na nód amháin (nó sraith bheag acu) é a laghdú go dtí rud ar bith. Mar shampla, is duine singil gan cairde ina gcónaí ina chomhpháirt comhdhéanta de rinn amháin, agus dá bhrí sin, ní bheidh an líon a bheith ag baint. Nó oileán trópaiceach iargúlta, ar a mbeidh daoine nach bhfuil aon teagmháil leis an domhan lasmuigh a bheidh, a bheith freisin ina chomhpháirt beag ar an líonra, lena ndaingnítear a neamhréir.

líonra domhanda de chairde

Ach tá rud éigin eile. Mar shampla, tá léitheoir an leabhar tóir cairde a d'fhás aníos i dtíortha eile, agus a dhéanann iad a chomhdhéanann í amháin. Má thógaimid san áireamh na tuismitheoirí na cairde agus a gcairde, is iad seo daoine go léir chomh maith sa chomhpháirt céanna, cé go riamh go raibh siad chuala faoi an léitheoir, labhraíonn teanga eile seachas, agus riamh in aice leis é a bheith. Dá bhrí sin, cé go bhfuil an líonra domhanda de cairdeas - nach raibh baint acu, an léitheoir a chur san áireamh sa chomhpháirt an-mhór, penetrating do gach cearn den domhan, lena n-áirítear daoine ó chúlraí éagsúla agus, go deimhin tá, ina gcuid shuntasach de dhaonra an domhain.

An rud céanna a tharlaíonn i sraitheanna sonraí líonra - tá mór, líonraí casta go minic ina chomhpháirt is mó, lena n-áirítear cuid mhaith de gach nód. Ina theannta sin, nuair a áirítear an líonra comhpháirt mó, tá sé beagnach i gcónaí ach amháin. A thuiscint cén fáth, tá sé riachtanach chun dul ar ais chuig an sampla de líonra domhanda de cairdeas agus iarracht a shamhlú go bhfuil dhá chomhpháirt is mó, gach ceann acu i gceist milliúin daoine. Caithfidh sé a bheith rib amháin ar chuid de na chéad chomhábhar don dara go dhá chomhpháirt is mó chumasc i amháin. Ós rud é ach chiumhais tosaigh amháin, i bhformhór na gcásanna go bhfuil sé improbable nach raibh sé déanta, agus dá bhrí sin ní tá uasmhéid dhá chomhpháirt i líonraí fíor breathnaíodh.

I roinnt cásanna neamhchoitianta, nuair an dá chomhpháirt den uasmhéid comh-ann ar feadh i bhfad i líonra fíor, bhí a n-aontas gan choinne, drámaíochta, agus, ar deireadh thiar, tá iarmhairtí tubaisteacha.

cumasc a chomhdhéanann í Timpiste

Mar shampla, tar éis teacht na taiscéalaithe Eorpacha i sibhialtacht na Leathsféar an Iarthair thart ar leath na Mílaoise ó shin, bhí cataclysm domhanda. Ó thaobh an líonra, d'fhéach sé mar seo: cúig mhíle bliain de líonra sóisialta domhanda, is dócha comhdhéanta de dhá chomhpháirt ollmhór - ceann i Meiriceá Thuaidh agus Theas, agus an ceann eile - i Eurasia. Ar an gcúis sin, tá an teicneolaíocht chun cinn go neamhspleách sa dá chomhpháirt, agus, níos measa fós, mar a d'fhorbair agus galar daonna, agus mar sin de. D. Nuair a fuair an dá chomhábhar ar deireadh i dteagmháil teicneolaíocht agus galar go tapa agus disastrously overflowed dara.

American High School

Is é an coincheap an chomhpháirt is mó úsáideach le haghaidh réasúnaíocht faoi líonraí ar scála i bhfad níos lú. Is sampla suimiúil graf a léiríonn an gaol i scoil Poist ard don tréimhse 18-mhí. Is é an bhfíric go bhfuil sé an chomhpháirt is mó fíor-riachtanach nuair a thagann sé chun an leathadh galar, galar gnéas-tarchurtha, a bhfuil an cuspóir an staidéir. Is féidir le daltaí a bhí ach páirtí amháin le linn na tréimhse sin ama, ach, mar sin féin, i ngan fhios, a bheith mar chuid de na comhpháirteanna an t-uasmhéid, agus dá bhrí sin, mar chuid de bhealach a d'fhéadfadh go leor de tarchuir. Léiríonn na struchtúir caidreamh fhéadfadh a bheith dar críoch fada, ach ceangal acu le daoine aonair i slabhraí ró-fhada, a bheith ar faoi réir ag scrúdú dian agus gossip. Mar sin féin, tá siad fíor: conas atá fíricí sóisialta dofheicthe, ach macrostructures iarmhartacha chun cinn mar tháirge na hidirghabhála ar leith.

Fad agus leithead-an chéad cuardaigh

Chomh maith leis an eolas faoi cé acu dhá nóid bhfuil baint acu bealach, ceadaíonn teoiric graf san eolaíocht ríomhaireachta tú eolas a fháil ar a fhad - in iompar, cumarsáid nó scaipeadh nuachta agus galair, chomh maith le cé acu a théann sé trí roinnt beanna nó níos mó.

Chun seo a dhéanamh, a shainiú ar fad bealach is comhionann leis an líon na céimeanna go bhfuil sé ó thús go deireadh, ie. E. Líon na imill san ord atá. Mar shampla, an t-MIT bealach, BBN, RAND, tá UCLA fad de 3, agus MIT, UTAH - 1. Bain úsáid as an fad an chosáin, is féidir linn a rá go, má tá dhá nóid suite sa cholún gar dá chéile nó i bhfad: Is é an t-achar idir an dá bhinn an sainmhíniú fad an cosán is giorra eatarthu. Mar shampla, is é an t-achar idir an LINC agus Srí 3, áfach, sin a chinntiú, tá sé riachtanach an t-easpa comhfhad a fhíorú go 1 nó 2, therebetween.

algartam cuardaigh Leithead-an chéad

Ar mhaithe le fad graf beag idir dhá nóid ríomh go héasca. Ach do casta tá gá le modh córasach achair a chinneadh.

An bealach is nádúrtha chun é seo agus, dá bhrí sin, is é an is éifeachtaí seo a leanas (mar shampla, líonra domhanda de chairde):

• Gach cairde a dhearbhú suite ar fad de 1.
• Gach cairde de chairde (ní comhaireamh an a luadh cheana) a fógraíodh ag fad 2.
• Gach a gcairde (arís, ní comhaireamh na daoine lipéadaithe) D'fhógair ar fad iargúlta 3.

Ag leanúint ar an mbealach seo, tá an cuardach a dhéantar i sraitheanna ina dhiaidh sin, gach ceann acu - ar an t-aonad ar an cheann roimhe sin. Tá gach sraith nua comhdhéanta de nóid nár ghlac páirt sa na cinn roimhe seo, agus a thagann imeall ó rinn an ciseal roimhe sin.

Tá an teicníc a dtugtar cuardaigh leithead-an chéad, mar cuardaigh sí ar an gcolún as an nód tosaigh, go príomha ag clúdach an chéad cheann eile. Chomh maith le modh chun faid a chinneadh, is féidir é a úsáid mar chreat coincheapúil úsáideach a eagrú ar an struchtúr graf chomh maith le conas a thógáil graf de ríomhaire, a beanna atá bunaithe ar a bhfad ó phointe tosaithe fosaithe.

Is féidir le cuardach Leithead-an chéad a chur i bhfeidhm, ní hamháin le líonra de chairde, ach freisin le haon ghraf.

domhan beag

Má théann tú ar ais go dtí líonra domhanda cairde, is féidir leat a fheiceáil go bhfuil an argóint go Míníonn bhaineann leis an chomhpháirt is mó fhormheasann rud éigin níos mó: nach bhfuil ach an léitheoir bealaí do chairde, ag nascadh dó le sciar suntasach de dhaonra an domhain, ach tá na bealaí ionadh gearr .

Is é an smaoineamh a dtugtar an "feiniméan domhan beag": is cosúil leis an domhan beag, má cheapann tú faoi na rudaí a nascann bealach gearr bith beirt.

An teoiric "sé handshakes" a bhí ar dtús imscrúdú turgnamhach ag Stanley Milgram agus a chomhghleacaithe sna 1960í. Gan aon tacar sonraí líonra sóisialta, agus le buiséad de $ 680, shocraigh sé chun seiceáil amach smaoineamh tóir. Chun na críche sin, d'iarr sé 296 thionscnóirí roghnú go randamach iarracht chun litir a sheoladh chuig an stocbhróicéir, a bhí ina gcónaí i mbruachbhaile de Boston. Tugadh thionscnóirí eolas pearsanta mar gheall ar an cuspóir (lena n-áirítear seoladh agus gairm), agus bhí siad a sheoladh litir chuig an duine a bhfuil a fhios acu de réir ainm, leis na treoracha céanna, ionas gur shroich sé an sprioc chomh tapa agus is féidir. Tá gach litir chuaigh tríd na lámha ar roinnt cairde agus déanta Dúnann slabhra do bróicéirí stoc lasmuigh de Boston.

I measc na 64 slabhraí a bhfuil bainte amach an sprioc, ba é an meánfhad sé, chun an líon ainmnithe fiche bliain níos luaithe sa dráma Dzhona Gera teideal.

In ainneoin go léir ar na lochtanna an staidéir, léirigh an turgnamh ar cheann de na gnéithe is tábhachtaí dár dtuiscint ar na líonraí sóisialta. Sna blianta ina dhiaidh sin as ndearnadh é a thabhairt i gcrích níos leithne: líonraí sóisialta claonadh go bhfuil bealaí an-ghearr idir péirí treallach daoine. Agus fiú amháin más rud é nach bhfuil naisc neamhdhíreacha den sórt sin le ceannairí gnó agus ceannairí polaitiúla a íoc ar a son féin ar bhonn laethúil, drámaí go bhfuil bealaí gearrthurais a leithéid de ról mór i an luas scaipeadh faisnéise, galar agus cineálacha eile ionfhabhtú sa phobal, chomh maith le rochtain ar na deiseanna a sholáthraíonn líonrú sóisialta daoine a bhfuil go maith na cáilíochtaí os coinne.