Grafieke in rekenaarwetenskap: definisie, tipes, aansoek voorbeelde. Grafiekteorie in rekenaarwetenskap

Tellings in die rekenaar metode vir die bepaling van verhoudings gekombineer elemente. Dit is die basiese oogmerke van studie in grafiekteorie.

basiese definisies

Wat is in die grafiek in rekenaarwetenskap? Dit sluit in 'n pluraliteit van voorwerpe genoem nodes of hoekpunte, sommige pare wat verbind is deur m. N. ribbes. Byvoorbeeld, die grafiek in die figuur (a) bestaan uit vier nodes, aangedui A, B, C, en D, B van wat verbind is aan elk van die ander drie hoekpunte ribbes, en C en D word ook in verband staan. Twee nodes is aangrensend as hulle met mekaar verbind deur 'n voorsprong. Die figuur toon 'n tipiese manier van hoe om grafieke in rekenaarwetenskap te bou. Sirkels verteenwoordig die hoekpunte en die lyne verbind elke paar van hulle, is die ribbes.

Wat ongerigte grafiek genoem in rekenaarwetenskap? Hy betrekkinge tussen die twee onder-ente van die ribbes is simmetries. Rib net verbind hulle met mekaar. In baie gevalle, egter, is dit nodig om die asimmetriese verhouding uit te druk - byvoorbeeld dat A punte na B, maar nie andersom nie. Hierdie doelwit is die definisie van die grafiek in die rekenaar, nog bestaan uit 'n stel van nodes met 'n stel van gerig kante. Elke georiënteerde rand is die skakel tussen hoekpunte wie se rigting het betekenis. Gerig grafieke uitbeeld, soos getoon in Figuur (b), is hul rande verteenwoordig deur pyle. As jy wil om te beklemtoon dat nie-directional grafiek, is dit ongerigte genoem.

netwerk modelle

Grafieke in rekenaarwetenskap is wiskundige model van die netwerk strukture. Die volgende figuur toon die struktuur van die Internet, dan gedra die naam van die ARPANET, in Desember 1970, toe sy net 13 punte. Die knope is die verwerking van sentrums en die ribbes verbind die twee hoekpunte waards therebetween. As jy nie aandag gee aan die Verenigde State van Amerika die kaart opgelê, die res van die beeld is 'n 13-node grafiek soortgelyk aan die vorige een. In hierdie geval, die werklike posisie van die toppunt is nie noodsaaklik nie. Dit is belangrik om wat nodes verbind aan mekaar.

Toepassing van grafieke in die rekenaar toelaat om te sien hoe dinge fisies of logies verbind in 'n netwerk struktuur. 13-node ARPANET is 'n voorbeeld van kommunikasienetwerk waarin top rekenaars of ander toestelle boodskappe kan oordra, en die kante verteenwoordig direkte skakel waarop inligting oorgedra kan word.

roetes

Hoewel die grafieke gebruik word in baie verskillende gebiede, het hulle algemene kenmerke. Grafiekteorie (rekenaarwetenskap) sluit dalk die belangrikste van hulle - die idee dat dinge beweeg dikwels langs die kante, agtermekaar beweeg van node te knoop, of dit nou 'n passasier 'n paar vlugte of inligting oorgedra van persoon tot persoon in 'n sosiale netwerk, of 'n gebruiker rekenaar, konsekwent besoek aan 'n aantal webblaaie deur die skakels.

Hierdie idee motiveer die definisie van die roete as 'n reeks van nodes verbind deur kante. Soms is dit nodig om die roete wat nie net komponente bevat, maar ook die volgorde van kante verbind hulle oorweeg. Byvoorbeeld, die volgorde van hoekpunte MIT, BBN, RAND, UCLA is 'n roete in ARPANET internet grafiek. Gedeelte van knope en rande kan herhaal word. Byvoorbeeld, SRI, STAN, UCLA, SRI, Utah, MIT is ook 'n roete. Die wyse waarop die ribbes nie herhaal word, bekend as 'n ketting. As die nodes nie herhaal word, staan dit as 'n eenvoudige ketting.

siklusse

Veral belangrik spesies in rekenaar grafieke - dit siklusse wat 'n ringstruktuur verteenwoordig, soos 'n reeks van nodes LINC, CASE, CARN, Harv, BBN, MIT, LINC. Roetes met ten minste drie ribbes, waarin die eerste en laaste knoop is dieselfde, en die res is anders, verteenwoordig 'n sikliese grafieke in rekenaarwetenskap.

Voorbeelde: SRI siklus, STAN, UCLA, SRI is die kortste, en Sri, STAN, UCLA, RAND, BBN, Utah, SRI aansienlik groter.

Feitlik elke ARPANET rand van die grafiek behoort aan die siklus. Dit is doelbewus gedoen, indien enige van hulle misluk, sal die moontlikheid van oorgang van een node na 'n ander. Siklusse in kommunikasie en vervoer stelsels is teenwoordig vir ontslag - hulle bied alternatiewe roetes vir 'n ander fietspad. Die sosiale netwerke is dikwels opvallend siklusse. As jy vind, byvoorbeeld dat 'n beslote skoolmaat van 'n neef van jou vrou eintlik werk met jou broer, dit is 'n siklus wat bestaan uit jou, jou vrou, haar neef, sy vriend uit die skool, sy werknemer (bv. E. Jou broer), en uiteindelik jou weer.

Verbind grafiek: definisie (rekenaarwetenskap)

Dit is natuurlik om te wonder of dit moontlik is uit elke node om aan enige ander node kry. Die grafiek is verbind as daar 'n pad tussen elke paar van die hoekpunte. Byvoorbeeld, die ARPANET netwerk - verbind grafiek. Dieselfde kan gesê word oor die meerderheid van kommunikasie en vervoer netwerke, as hul doel is om verkeer uit een node na 'n ander.

Aan die ander kant, is daar geen a priori rede om te verwag dat hierdie soort van grafieke in rekenaarwetenskap is wydverspreid. Byvoorbeeld, in die sosiale netwerk is nie moeilik om te twee mense wat nie verwant is aan mekaar dink.

komponente

As die kolom is nie verbonde aan die rekenaar, wat hulle natuurlik val in 'n stel verwante fragmente, groepe van nodes wat geïsoleer en nie sny. Byvoorbeeld, figuur toon drie sulke dele: die eerste - A en B, die tweede - C, D en E, en die derde bestaan uit die oorblywende hoekpunte.

Komponente van die grafiek verteenwoordig 'n subset van nodes, waarin:

• elke hoekpunt subgroep het 'n roete na 'n ander;
• subset is nie deel van 'n groter stel waarin elke node 'n roete na 'n ander.

Wanneer die grafieke in rekenaar is verdeel in hul komponente, dit is net die eerste beskrywing van die metode van hul struktuur. Hierdie komponent kan ryk in die interne struktuur wees, is dit belangrik vir die interpretasie van die netwerk. Byvoorbeeld, die formele metode van bepaling van 'n node belang is om vas te stel hoeveel dele verdeel sal word telling, of die node verwyder.

maksimum komponent

Daar is 'n metode vir kwalitatiewe assessering van verbinding komponente. Byvoorbeeld, daar is 'n wêreldwye sosiale netwerk met verbande tussen twee mense, al is hulle vriende.

Is dit verbind? Waarskynlik nie. Verbinding - eerder broos eiendom, en die gedrag van een node (of 'n klein stel van hulle) kan dit verminder tot niks. Byvoorbeeld, 'n enkele persoon met geen lewende vriende is 'n komponent wat bestaan uit 'n enkele toppunt, en dus sal die telling nie gekoppel word. Of 'n afgeleë tropiese eiland, wat bestaan uit mense wat geen kontak met die buitewêreld, sal ook 'n klein komponent van die netwerk, wat sy onsamehangendheid bevestig wees.

Wêreldwye netwerk van vriende

Maar daar is iets anders. Byvoorbeeld, 'n leser van die gewilde boek het vriende wat in ander lande het gegroei, en maak hulle een komponent. As ons in ag neem die ouers van hierdie vriende en hul vriende, al hierdie mense is ook in dieselfde komponent, hoewel hulle nog nooit gehoor van die leser, praat 'n ander taal, en langs dit was nog nooit. Dus, hoewel die wêreldwye netwerk van vriendskap - nie verbind is, die leser sal ingesluit word in die komponent is baie groot, indringende na alle dele van die wêreld, wat mense uit baie verskillende agtergronde sluit en, in werklikheid, bevat 'n beduidende gedeelte van die wêreld se bevolking.

Dieselfde gebeur in die netwerk data stelle - groot, komplekse netwerke het dikwels 'n maksimum komponent, wat 'n belangrike deel van al die nodes sluit. Verder, wanneer die netwerk sluit 'n maksimum komponent, is dit byna altyd net een. Om te verstaan waarom dit nodig is om terug na die voorbeeld van 'n wêreldwye netwerk van vriendskap gaan en probeer om die bestaan van twee maksimum komponente, wat elkeen behels miljoene mense dink. Dit moet 'n enkele rib op 'n paar van die eerste komponent van die tweede tot 'n maksimum twee komponente saamgesmelt in een hê. Aangesien slegs een kant, in die meeste gevalle is dit onwaarskynlik dat dit nie gestig, en dus maksimum twee komponente in real netwerke nooit waargeneem.

In sommige gevalle, wanneer die twee komponente van die maksimum-mede bestaan vir 'n lang tyd in 'n werklike netwerk, hul unie was onverwags, dramatiese, en, uiteindelik, het katastrofiese gevolge.

Ongeluk komponent samesmelting

Byvoorbeeld, na die aankoms van Europese ontdekkingsreisigers in die beskawing van die Westelike Halfrond oor die helfte van 'n duisend jaar gelede, was daar 'n globale ramp. Van die oogpunt van die netwerk, dit lyk soos hierdie: vyfduisend jaar van globale sosiale netwerk, waarskynlik bestaan uit twee reuse komponent - een in Noord-en Suid-Amerika, en die ander - in Eurasië. Om hierdie rede, het die tegnologie onafhanklik ontwikkel in die twee komponente, en, nog erger, soos ontwikkel en menslike siekte, en so aan. D. Wanneer die twee komponente uiteindelik in aanraking tegnologie en 'n siekte vinnig en rampspoedig oorstroom tweede.

Amerikaanse High School

Die konsep van die maksimum komponent is nuttig vir redenasie oor netwerke op 'n baie kleiner skaal. 'N Interessante voorbeeld is 'n grafiek illustreer die verhouding in 'n Amerikaanse hoërskool vir die tydperk van 18 maande. Die feit dat dit die maksimum komponent bevat is noodsaaklik wanneer dit kom by die verspreiding van siektes, seksueel oordraagbare siektes, wat is die doel van die studie. Studente mag slegs een maat gehad het gedurende daardie tydperk, maar, nietemin, sonder dat hulle dit besef, het deel van die komponente van die maksimum is, en dus 'n deel van baie potensiaal roetes van oordrag. Hierdie strukture weerspieël 'n verhouding wat lank mag geëindig het, maar hulle verbind individue in te lank kettings, om die onderwerp van intense ondersoek en skinder wees. Nietemin, hulle is 'n werklikheid: hoe sosiale feite is onsigbare, maar gevolglike macrostructures na vore gekom as 'n produk van individuele bemiddeling.

Afstand en breedte-eerste soek

In bykomend tot die inligting oor die vraag of twee nodes verbind roete, grafiekteorie in rekenaarwetenskap kan jy leer oor die lengte - in vervoer, kommunikasie of verspreiding van nuus en siektes, asook of dit gaan deur verskeie pieke of meerdere.

Om dit te doen, definieer 'n roete lengte gelyk aan die aantal stappe wat dit bevat, van begin tot einde, dit wil sê. E. Die aantal rande in die volgorde wat. Byvoorbeeld, MIT, BBN, RAND, UCLA roete het 'n lengte van 3, en MIT, Utah - 1. Die gebruik van die lengte van die pad, kan ons sê dat indien twee nodes gerangskik in die kolom naby aan mekaar of ver afstand tussen die twee pieke word gedefinieer as die lengte van die kortste pad tussen hulle. Byvoorbeeld, die afstand tussen die LINC en Sri is 3, al is, om dit te verseker, is dit nodig om die afwesigheid van lengte gelyk te verifieer om 1 of 2, therebetween.

Breedte-eerste soekalgoritme

Vir klein grafiek afstand tussen twee nodes bereken maklik. Maar vir 'n komplekse is daar 'n behoefte aan 'n sistematiese metode van bepaling van afstande.

Die mees natuurlike manier om dit te doen en dus die mees doeltreffende is die volgende (byvoorbeeld, 'n wêreldwye netwerk van vriende):

• Alle vriende verklaar geleë op 'n afstand van 1.
• Alle vriende van vriende (nie die tel van die reeds genoemde) is aangekondig by afstand 2.
• Al hulle vriende (weer, nie die tel van die benoemde persone) aangekondig op afgeleë afstand 3.

op die eenheid op die vorige een - die voortsetting in hierdie manier, die soektog is in die daaropvolgende lae gedra, wat elkeen. Elke nuwe laag bestaan uit nodes wat nie deelgeneem het aan die voriges, en dat val rand van die toppunt van die vorige laag.

Hierdie tegniek staan bekend as 'n breedte-eerste soek, as sy soek na die kolom uit die aanvanklike node, in die eerste plek oor die volgende. In bykomend tot die verskaffing van 'n metode vir die bepaling van afstande, kan dit dien as 'n nuttige konseptuele raamwerk om die grafiek struktuur te organiseer, asook hoe om 'n grafiek van die rekenaar te bou, met pieke op grond van hul afstand vanaf 'n vaste vertrekpunt.

Breedte-eerste soek toegepas kan word om nie net 'n netwerk van vriende, maar ook om 'n grafiek.

klein wêreld

As jy terug gaan na 'n wêreldwye netwerk van vriende, kan jy sien dat die argument wat verduidelik wat deel uitmaak van die maksimum komponent regtig iets meer keur: nie net die leser roetes na vriende, hom met 'n skakel met 'n belangrike deel van die wêreld se bevolking, maar hierdie roetes is verbasend kort .

Hierdie idee is bekend as die "klein wêreld verskynsel": die wêreld lyk klein, as jy dink oor wat 'n kort roete verbind enige twee mense.

Die teorie van "ses handdrukke" is die eerste keer eksperimenteel ondersoek deur Stanley Milgram en sy kollegas in die 1960's. Sonder enige stel sosiale netwerk data, en met 'n begroting van $ 680, het hy besluit om te kyk na 'n gewilde idee. Vir hierdie doel, vra hy 296 lukraak gekies inisieerders probeer om 'n brief aan die aandelemakelaar, wat in 'n voorstad van Boston gewoon. Inisieerders gegee sommige persoonlike inligting oor die doel (insluitende adres en beroep), en hulle het 'n brief aan die persoon vir wie hulle geweet by die naam te stuur, met dieselfde instruksies, sodat dit die doel om so gou moontlik bereik. Elke brief het deur die hande van 'n aantal vriende geslaag en vorm n ketting sluit vir aandelemakelaars buite Boston.

Onder die 64 kettings wat die teiken bereik het, die gemiddelde lengte was ses, wat bevestig dat die aantal vernoem twee dekades vroeër in die spel Dzhona Gera titel.

Ten spyte van al die tekortkominge van hierdie studie, die eksperiment gedemonstreer een van die belangrikste aspekte van ons begrip van die sosiale netwerke. In die jare wat gevolg het daaruit gemaak breër gevolgtrekking: sosiale netwerke is geneig om baie kort roetes tussen arbitrêre pare van mense. En selfs al is so 'n indirekte bande met sakeleiers en politieke leiers nie betaal vir hulself op 'n daaglikse basis, die bestaan van so 'n kort roetes speel 'n groot rol in die spoed van inligtingverspreiding, siekte en ander vorme van infeksie in die gemeenskap, sowel as toegang die geleenthede wat sosiale netwerk bied mense met presies die teenoorgestelde eienskappe.