Grafice în informatică: definiție, tipuri, aplicații, exemple. Teoria graficelor în știința informaticii

Graficele din informatică reprezintă o modalitate de a defini relațiile într-o combinație de elemente. Acestea sunt principalele obiecte de studiu teoria graficelor.

Definiții de bază

Ce reprezintă graficul din știința calculatoarelor? Acesta include un set de obiecte numite noduri sau noduri, unele perechi fiind asociate cu așa-numitele. coaste. De exemplu, graficul din figura (a) constă din patru noduri, desemnate A, B, C și D, dintre care B este conectat la fiecare dintre celelalte trei vârfuri prin margini, iar C și D sunt de asemenea conectate. Două noduri sunt adiacente dacă sunt conectate printr-o margine. Figura arată o modalitate tipică de a construi grafice în domeniul informaticii. Cercurile reprezintă vârfurile, iar liniile care leagă fiecare pereche sunt coaste.

Ce graf se numește ne-orientat în domeniul informaticii? Relația dintre cele două capete ale coastei este simetrică. Ribul le leagă pur și simplu unul de celălalt. În multe cazuri, cu toate acestea, este necesar să se exprime relații asimetrice - de exemplu, că A indică spre B, dar nu invers. Acest obiectiv este definit de definiția unui grafic din informatică, care mai conține un set de noduri, împreună cu un set de muchii orientate. Fiecare margine orientată este o conexiune între vârfuri, a cărei direcție are o valoare. Graficele direcționate sunt reprezentate așa cum se arată în figura (b), marginile lor fiind reprezentate de săgeți. Atunci când este necesar să se sublinieze că graficul este nedirecționat, se numește nedirecționat.

Modele de rețele

Graficele din știința calculatoarelor servesc model matematic structuri de rețea. Următoarea figură prezintă structura internetului, numită apoi ARPANET, în decembrie 1970, când avea doar 13 puncte. Nodurile sunt centre de calcul, iar marginile conectează două vârfuri cu o conexiune directă între ele. Dacă nu acordați atenție hărții superimpuse a SUA, restul imaginii este un grafic cu 13 noduri similar cu cel precedent. În acest caz, aranjarea reală a nodurilor este nesemnificativă. Este important care sunt nodurile conectate una la alta.

Utilizarea graficelor în știința informaticii vă permite să vă imaginați cum lucrurile sunt legate fizic sau logic între ele în structura rețelei. ARPANET-ul cu 13 noduri este un exemplu de rețea de comunicații în care vârfurile computerului sau alte dispozitive pot transmite mesaje, iar marginile sunt legături directe pe care pot fi transmise informații.

rute

Deși graficele sunt folosite în multe domenii diferite, ele au caracteristici comune. Teoria grafurilor (informatică) include, probabil, cel mai important dintre ele - ideea că lucrurile se mișcă de multe ori de-a lungul marginilor, se deplasează secvențial de la un nod la altul, fie că este vorba un pasager câteva zboruri sau informații transmise de la persoană la persoană într-o rețea socială sau un utilizator computer, vizitând secvențial o serie de pagini web, urmând legăturile.

Această idee motivează definirea unei rute ca o succesiune de vârfuri conectate de margini. Uneori este necesar să se ia în considerare un traseu care conține nu numai noduri, ci și secvența marginilor care le conectează. De exemplu, secvența de vârfuri MIT, BBN, RAND, UCLA este o rută în graficul Internet ARPANET. Trecerea de noduri și muchii poate fi repetată. De exemplu, SRI, STAN, UCLA, SRI, UTAH, MIT este, de asemenea, un traseu. Calea în care marginile nu se repetă se numește lanț. Dacă nodurile nu se repetă, se numește lanț simplu.

cicluri

Graficele deosebit de importante în știința informaticii sunt ciclurile, care reprezintă o structură inelară, cum ar fi secvența de noduri LINC, CASE, CARN, HARV, BBN, MIT, LINC. Rutele cu cel puțin trei margini, în care primul și ultimul nod sunt identice și celelalte sunt diferite, sunt grafice ciclice în domeniul informaticii.

Exemple: ciclu SRI, STAN, UCLA, SRI este cel mai scurt, iar SRI, STAN, UCLA, RAND, BBN, UTAH, SRI este mult mai mare.

Practic, fiecare margine ARPANET a graficului aparține ciclului. Acest lucru a fost făcut în mod deliberat, în cazul în care nici una dintre ele nu reușește, va posibilitatea de tranziție de la un nod la altul. Cicluri în comunicațiile și sistemele de transport sunt prezente pentru redundanță - acestea oferă rute alternative pentru o altă cale de ciclu. Într-o rețea socială, de asemenea, se observă adesea cicluri. Când găsiți, de exemplu, că un prieten școală apropiat de un văr de soția ta, de fapt lucrează cu fratele tău, acesta este un ciclu care constă din tine, soția ta, vărul ei, prietenul său de la școală, angajat al său (de ex., E. dvs. frate) și, în cele din urmă, din nou voi.

Grafic conectat: definiție (informatică)

Este normal să ne întrebăm dacă este posibil să ajungem de la fiecare nod la orice alt nod. Un grafic este coerent dacă există o rută între fiecare pereche de vârfuri. De exemplu, rețeaua ARPANET este un grafic conectat. Același lucru se poate spune despre majoritatea rețelelor de comunicații și de transport, deoarece scopul lor este de a direcționa traficul de la un nod la altul.

Pe de altă parte, nu există niciun motiv a priori de a ne aștepta ca aceste tipuri de grafice din domeniul informaticii să fie larg răspândite. De exemplu, într-o rețea socială nu este greu de imaginat două persoane care nu au legătură între ele.

componente

Dacă graficele din știința calculatoarelor nu sunt conectate, atunci ele se descompun în mod natural într-un set de fragmente conexe, grupuri de noduri care sunt izolate și nu se intersectează. De exemplu, figura prezintă trei astfel de părți: primul - A și B, al doilea - C, D și E, iar al treilea constă din restul vârfurilor.

Componentele unei conectivități grafice sunt un subset de noduri care au:

• fiecare vârf al subgrupului are un traseu către oricare altul;
• Un subset nu face parte dintr-un set mai mare în care fiecare nod are un traseu către oricare altul.

Când graficele din știința informaticii sunt împărțite în componentele lor, acesta este doar modul inițial de a descrie structura lor. În cadrul acestei componente poate exista o structură internă bogată, importantă pentru interpretarea rețelei. De exemplu, o metodă formală de determinare a importanței unui nod este de a determina câte părți împart graficul, dacă nodul este eliminat.

Componenta maximă

Există o metodă de evaluare calitativă a componentelor de conectivitate. De exemplu, există o rețea socială globală cu legături între două persoane, dacă sunt prieteni.

Este conectată? Probabil că nu. Conectarea este o proprietate destul de fragilă, iar comportamentul unui nod (sau un mic set de ele) îl poate anula. De exemplu, o persoană fără prieteni live va fi o componentă formată dintr-un singur punct și, prin urmare, graficul nu va fi conectat. Sau o insulă tropicală îndepărtată, formată din oameni care nu au contact cu lumea exterioară, va fi, de asemenea, o mică componentă a rețelei, ceea ce confirmă incoerența acesteia.

Rețeaua globală de prieteni

Dar există și altceva. De exemplu, un cititor de populara carte are prieteni care au crescut în alte țări, și le face un component. Dacă luăm în considerare părinții acestor prieteni și prietenii lor, toți acești oameni sunt, de asemenea, în aceeași componentă, cu toate că nu au auzit niciodată despre cititor, vorbesc o altă limbă, și lângă ea nu a fost niciodată. Astfel, deși rețeaua globală de prietenie - nu este conectat, cititorul va fi inclus în componenta sunt foarte mari, pătrunzând în toate părțile lumii, care include oameni din medii diferite și, de fapt, conține o parte semnificativă a populației lumii.

Același lucru este valabil și pentru seturile de date în rețea - rețelele mari, complexe au adesea o componentă maximă care include o parte semnificativă din toate nodurile. Mai mult, atunci când rețeaua conține componenta maximă, este aproape întotdeauna doar una. Pentru a înțelege de ce ar trebui să ne întoarcem la exemplul cu o rețea globală de prietenie și să încercăm să ne imaginăm prezența a două componente maximale, fiecare dintre care include milioane de oameni. Aceasta va necesita prezența unei singure margini de la una din prima componentă la cea de-a doua, astfel încât cele două componente maxime să se integreze într-una. Deoarece marginea este unică, în majoritatea cazurilor este de necrezut că nu se formează și deci cele două componente maxime din rețelele reale nu sunt niciodată observate.

În unele cazuri rare, când cele două componente maximale coexistau mult timp într-o rețea reală, unificarea lor a fost neașteptată, dramatică și, în cele din urmă, a avut consecințe catastrofale.

Fuziunea componentelor

De exemplu, după sosirea cercetătorilor europeni în civilizația emisferei occidentale, cu aproximativ o jumătate de mileniu în urmă, a avut loc un cataclism global. Din punct de vedere al rețelei, arăta astfel: de cinci mii de ani, rețeaua socială globală, probabil, a constat din două componente gigantice - una în America de Nord și de Sud și cealaltă în Eurasia. Din acest motiv, s-au dezvoltat tehnologii dezvoltate independent în două componente și, chiar mai rău, boli umane, etc., când cele două componente au intrat în contact în cele din urmă, tehnologiile și bolile unuia umplut rapid și catastrofal cel de-al doilea.

Liceul american

Conceptul de componente maximale este util pentru raționamentul privind rețelele și în dimensiuni mult mai mici. Un exemplu interesant este un grafic care ilustrează relația romantică în liceul american pentru o perioadă de 18 luni. Faptul că aceasta conține componenta maximă este importantă în ceea ce privește răspândirea bolilor cu transmitere sexuală, care a fost scopul studiului. Elevii ar fi putut avea un singur partener pentru această perioadă de timp, dar, fără să realizeze acest lucru, aceștia făceau parte din componenta maximă și, prin urmare, făceau parte din multe căi potențiale de transmisie. Aceste structuri reflectă relații care s-au încheiat mult timp, dar leagă indivizii în lanțuri prea mult timp pentru a deveni subiectul atenției și bârfei. Cu toate acestea, ele sunt reale: întrucât faptele sociale sunt invizibile, dar macrostructurile în mod logic curg, care au apărut ca un produs al medierii individuale.

Distanța și lungimea căutării

În plus față de informațiile cu privire la dacă două noduri sunt conectate traseu, teoria grafurilor în informatică vă permite să învețe despre lungimea sa - în domeniul transporturilor, comunicarea sau difuzarea de știri și a bolilor, precum și dacă acesta trece prin mai multe vârfuri sau multiple.

Pentru a face acest lucru, să definească o lungime rută egală cu numărul de pași pe care-l conține de la început până la sfârșit, adică. E. Numărul muchiilor din secvență care este. De exemplu, MIT, BBN, RAND, traseul UCLA are o lungime de 3, și MIT, UTAH - 1. Folosind lungimea traseului, putem spune că dacă două noduri sunt aranjate în coloana aproape fiecare distanță cealaltă sau departe între cele două vârfuri este definită ca lungimea calea cea mai scurtă dintre ele. De exemplu, distanța dintre Linc și SRI este de 3, deși, pentru a asigura acest lucru, este necesar să se verifice absența lungimii egală cu 1 sau 2, acestea.

Algoritmul de căutare în lățime

Pentru graficele mici, distanța dintre două noduri poate fi ușor calculată. Dar, pentru cele complexe, este nevoie de o metodă sistematică de determinare a distanțelor.

Cea mai naturală modalitate de a face acest lucru și, prin urmare, cea mai eficientă, este următoarea (pe exemplul unei rețele globale de prieteni):

• Toți prietenii sunt declarați a fi la distanță de 1.
• Toți prietenii prietenilor (cu excepția celor deja marcați) sunt declarați a fi localizați la o distanță de 2.
• Toți prietenii lor (din nou, fără a număra persoane marcate) sunt declarate la distanță de o distanță de 3.

Continuând astfel, căutarea se realizează în straturi ulterioare, fiecare dintre ele fiind o unitate dincolo de cea precedentă. Fiecare strat nou este alcătuit din noduri care nu au participat încă la cele anterioare și care intră în margine cu partea superioară a stratului anterior.

Această tehnică este numită căutare în lățime, deoarece ea caută graficul în afară de la nodul de pornire, în primul rând acoperind cele mai apropiate. În plus față de furnizarea unei metode de determinare a distanțelor, poate servi ca un cadru conceptual util pentru organizarea structurii graficului precum și modul de a construi un grafic de calculator, având picuri pe baza distanței de la un punct de plecare fix.

Căutarea în lățime poate fi aplicată nu numai rețelei de prieteni, ci și oricărui grafic.

Lumea este mică

Dacă te duci înapoi la o rețea globală de prieteni, puteți vedea că argumentul care explică aparținând componentei maxime aprobă într-adevăr ceva mai mult: nu numai că cititorul are rute la prieteni, care leagă-l cu o proporție semnificativă din populația lumii, dar aceste rute sunt surprinzător de scurt .

Această idee a fost numită "fenomenul unei lumi apropiate": lumea pare mică, dacă vă gândiți la ceea ce o ruta scurtă conectează oricare doi oameni.

Teoria "șase strângere de mână" a fost prima investigată experimental de Stanley Milgram și colegii săi în anii 1960. Nu are niciun set de date de rețele sociale și cu un buget de 680 de dolari, el a decis să verifice ideea populară. În acest scop, el a cerut 296 de inițiatori aleși în mod aleatoriu încerca să trimită o scrisoare către broker, care a trăit într-o suburbie din Boston. Inițiatori s-au dat unele informații personale despre scopul (inclusiv adresa si profesie), și au trebuit să trimită o scrisoare către persoana pe care au cunoscut după nume, cu aceleași instrucțiuni, astfel încât acesta a atins obiectivul cât mai repede posibil. Fiecare scrisoare a trecut prin mâinile unui număr de prieteni și a format un lanț închis pe un broker de schimb în afara orașului Boston.

Printre cele 64 de lanțuri care au atins scopul, lungimea medie a fost de șase, ceea ce a fost confirmat de numărul numit două decenii mai devreme în titlul piesei de către John Gare.

În ciuda tuturor deficiențelor acestui studiu, experimentul a demonstrat unul dintre cele mai importante aspecte ale înțelegerii rețelelor sociale. În anii care au urmat de la ea a fost făcută mai largă concluzie: rețelele sociale tind să aibă rute foarte scurte între perechile arbitrare de oameni. Și chiar dacă aceste legături indirecte cu liderii de afaceri și lideri politici nu plătesc pentru ele însele pe o bază de zi cu zi, existența unor astfel de rute scurte joacă un rol important în viteza de diseminare a informației, a bolilor și a altor tipuri de infecție în comunitate, precum și acces oportunitățile pe care rețelele sociale oferă oamenilor complet opuse calități.