Graficele în informatică: definiție, tipuri, exemple de aplicații. Teoria grafurilor în informatică

Numără în metoda de calculator pentru relațiile de determinare sunt elemente combinate. Acestea sunt obiectele de baza de studiu în teoria grafurilor.

definiții de bază

Ce este în grafic în informatică? Acesta include o multitudine de obiecte numite noduri sau noduri, niște perechi de care sunt conectate prin m. N. coaste. De exemplu, graficul din figura (a) este format din patru noduri, notate A, B, C și D, din care B este conectat la fiecare dintre celelalte trei coaste vârfuri, și C și D sunt conectate. Două noduri sunt adiacente în cazul în care acestea sunt conectate printr-o margine. Figura arată un mod tipic de modul de a construi grafice în informatică. Cercurile reprezintă nodurile și liniile de racordare fiecare pereche de ele, sunt coastele.

Ce graf neorientat este numit în informatică? El relațiile dintre cele două capete ale nervurilor sunt simetrice. Rib pur și simplu le conectează unele cu altele. În multe cazuri, cu toate acestea, este necesar să se exprime relația asimetrică - de exemplu, că un puncte de la B, dar nu și invers. Acest obiectiv este definirea graficului în calculator, încă este format dintr-un set de noduri cu un set de margini direcționate. Fiecare margine orientată este legătura dintre noduri a căror direcție are sens. grafice descriu dirijate, așa cum se arată în figura (b), marginile lor sunt reprezentate prin săgeți. Când doriți să sublinieze faptul că graficul non-direcțională, este numit nedirijate.

modelele de rețea

Graficele în informatică sunt modelul matematic al structurilor de rețea. Următoarea figură prezintă structura Internetului, apoi a purtat numele de ARPANET, în decembrie 1970, când ea a fost de doar 13 de puncte. Nodurile sunt centre de prelucrare și nervurile conecta două noduri feedforward între ele. Dacă nu acorde atenție în Statele Unite au impus hartă, restul imaginii este un grafic de 13-nod similar cu cel anterior. În acest caz, poziția reală a nodului nu este esențială. Este important la care nodurile sunt conectate între ele.

Aplicarea grafice din calculator permite pentru a vedea cum lucrurile sunt interconectate fie fizic, fie logic într-o structură de rețea. 13-nod ARPANET este un exemplu de rețea de comunicație în care calculatoarele de top sau alte dispozitive pot transmite mesaje, iar muchiile reprezintă o legătură directă, pe care pot fi transmise informații.

rute

Cu toate 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 calculator, vizitând în mod constant un număr de pagini web urmând link-urile.

Această idee motivează definirea traseului ca o serie de noduri conectate de margini. Uneori este necesar să se ia în considerare traseul pe care nu conține numai componente, dar, de asemenea, secvența de muchii conectându-le. De exemplu, secvența de noduri MIT, BBN, RAND, UCLA este un traseu în graficul de internet ARPANET. Trecerea de noduri și muchii pot fi repetate. De exemplu, SRI, STAN, UCLA, SRI, UTAH, MIT este o cale. Modul în care nervurile nu sunt repetate, numit un lanț. În cazul în care nodurile nu se repetă, se numește un lanț simplu.

cicluri

specii deosebit de importante în graficele de calculator - it cicluri care reprezintă o structură ciclică, cum ar fi o secvență de noduri LINC, CASE, CARN, HARV, BBN, MIT, LINC. Rutele cu cel puțin trei coaste, în care primul și ultimul nod sunt aceleași, iar restul sunt diferite, reprezintă un grafice ciclice în informatică.

Exemple: ciclul SRI, STAN, UCLA, SRI este cel mai scurt, iar SRI, STAN, UCLA, RAND, BBN, UTAH, SRI considerabil 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. Rețelele sociale sunt adesea cicluri vizibile. 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ă te din nou.

Grafic Connected: definiție (informatică)

Este firesc să ne întrebăm dacă este posibil din fiecare nod pentru a ajunge la orice alt nod. Graficul este conectat în cazul în care există o cale între fiecare pereche de noduri. De exemplu, rețeaua ARPANET - conectată grafic. Același lucru se poate spune despre majoritatea rețelelor de comunicații și de transport, ca scopul lor este de a direcționa traficul de la un nod la altul.

Pe de altă parte, nu există nici un motiv a priori să se aștepte ca aceste tipuri de grafice în știința calculatoarelor sunt larg răspândite. De exemplu, în rețeaua socială nu este greu de imaginat doi oameni care nu sunt legate între ele.

componente

În cazul în care coloana nu este conectat la calculator, acestea se încadrează în mod natural într-un set de fragmente înrudite, grupuri de noduri, care sunt izolate și nu se intersectează. De exemplu, Figura prezintă trei astfel de părți: prima - A și B, al doilea - C, D și E, iar al treilea este format din nodurile rămase.

Componentele graficului reprezintă un subset de noduri, în care:

• fiecare subgrup vertex are o cale spre orice alta;
• subgrup nu face parte dintr-un set mai mare, în care fiecare nod are o rută către oricare altul.

Atunci când graficele din calculator sunt împărțite în componentele lor, este doar descrierea inițială a metodei structurii lor. Această componentă poate fi bogat în structura internă, este important pentru interpretarea rețelei. De exemplu, metoda formală de determinare a unui nod este importanta pentru a determina cât de multe părți vor fi împărțite count, în cazul în care nodul este eliminat.

componentă maximă

Există o metodă de evaluare calitativă a componentelor de conectivitate. De exemplu, există o rețea socială la nivel mondial, cu conexiuni între două persoane, în cazul în care sunt prieteni.

Este conectat? Probabil că nu. Conectivitate - proprietate, mai degrabă fragilă, iar comportamentul unui nod (sau un mic set de ele) poate reduce la nimic. De exemplu, o singură persoană cu nici un prieten care trăiesc este o componentă constând dintr-un singur nod, și, prin urmare, numărul nu va fi conectat. Sau o insula tropicala de la distanță, format din persoane care nu au contact cu lumea exterioară, va fi, de asemenea, o componentă mică a rețelei, care confirmă incoerență acesteia.

rețea globală de prieteni

Dar mai e ceva. 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 se întâmplă în seturile de date de rețea - rețele mari, complexe au adesea o componentă maximă, care include o proporție semnificativă a tuturor nodurilor. Mai mult decât atât, atunci când rețeaua include o componentă maximă, este aproape întotdeauna doar unul. Pentru a înțelege de ce, este necesar să ne întoarcem la exemplul unei rețele globale de prietenie și să încerce să-și imagineze existența a două componente maxime, fiecare dintre care implică milioane de oameni. Acesta trebuie să aibă o singură nervură pe unele din primul component la al doilea la maximum două componente au fuzionat într-una singură. Deoarece numai o margine, în cele mai multe cazuri, este improbabil ca aceasta nu a fost format, și, prin urmare, maximum două componente în rețele reale nu sunt respectate.

În unele cazuri rare, atunci când cele două componente ale maxime de co-existat pentru o lungă perioadă de timp într-o rețea reală, unirea lor a fost neașteptată, dramatică, și, în cele din urmă, au consecințe catastrofale.

fuziune componenta accident

De exemplu, după sosirea de exploratorii europeni în civilizația din emisfera vestică aproximativ o jumătate de mileniu în urmă, a existat un cataclism la nivel mondial. Din punct de vedere al rețelei, arăta așa: cinci mii de ani de rețea socială la nivel mondial, probabil, a constat din două componente gigant - una în America de Nord și de Sud, iar celălalt - în Eurasia. Din acest motiv, tehnologia a evoluat în mod independent, în cele două componente, și, chiar mai rău, cum au fost dezvoltate și boala umană, și așa mai departe. D. Când în cele din urmă cele două componente a intrat în tehnologia touch si o boala rapid si catastrofal înecată de-al doilea.

American High School

Conceptul de componenta maximă este utilă pentru raționamentul despre rețele pe o scară mult mai mică. Un exemplu interesant este un grafic care ilustrează relația într-un liceu din SUA pentru perioada de 18 luni. Faptul că acesta conține componenta maximă este esențială atunci când vine vorba de răspândirea bolilor, bolilor cu transmitere sexuală, care este scopul studiului. Elevii pot avea un singur partener în acea perioadă de timp, dar, cu toate acestea, fără să-și dea seama, au făcut parte din componentele maxime, și, prin urmare, o parte din mai multe rute potențiale de transmitere. Aceste structuri reflectă o relație care poate fi încheiat cu mult, dar se vor conecta indivizi în lanțuri prea mult timp, să facă obiectul unor analize minuțioase și bârfe. Cu toate acestea, ele sunt reale: modul în care faptele sociale sunt invizibile, dar macrostructuri indirecte a apărut ca un produs al medierii individuale.

Distanța și lățimea prima căutare

Î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.

Latime-primul algoritm de căutare

Pentru distanta grafic mici între două noduri se calculează cu ușurință. Dar pentru complex este nevoie de o metodă sistematică de determinare a distanțelor.

Modul cel mai natural de a face acest lucru și, prin urmare, cea mai eficientă este următoarea (de exemplu, o rețea globală de prieteni):

• Toți prietenii sunt declarate situate la o distanță de 1.
• Toți prietenii de prieteni (nu de numărare deja menționate) sunt anunțate la o distanță de 2.
• Toți prietenii lor (din nou, nu de numărare oamenii etichetate) a anunțat pe distanța de la distanță 3.

Continuând în acest mod, căutarea se efectuează în straturi ulterioare, fiecare dintre care - pe unitate pe cea anterioară. Fiecare nou strat este compus din noduri care nu au participat la cele anterioare, și care se încadrează marginea din vârful stratului precedent.

Această tehnică se numește o căutare lățime mai întâi, în timp ce caută coloana din nodul inițial, care acoperă în primul rând următorul. Î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.

Breadth prima căutare poate fi aplicat nu numai la o rețea de prieteni, dar, de asemenea, la orice grafic.

Ce mică e lumea

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 se numește „fenomen lume mică“: lumea pare mic, dacă vă gândiți la ceea ce un scurt traseu leagă doi oameni.

Teoria „șase strângeri de mână“ a fost mai întâi experimental investigat de Stanley Milgram si colegii sai in anii 1960. Fără a avea orice set de date de rețele sociale, precum și cu un buget de $ 680 a decis să verifice o idee 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ț se închide pentru brokerii de stoc în afara Boston.

Dintre cele 64 de lanțuri care au atins ținta, lungimea medie a fost de șase ani, confirmând numărul numit de două decenii mai devreme în joc Dzhona Gera titlu.

În ciuda tuturor neajunsurile acestui studiu, experimentul a demonstrat unul dintre cele mai importante aspecte ale înțelegerii noastre a 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 destul calitățile opuse.