Grafi v informatikah: definicija, vrste, aplikacije, primeri. Teorija grafov v računalništvu

Grafi v informatiki so način določanja odnosov v kombinaciji elementov. To so glavni predmeti študije teorije grafov.

Osnovne definicije

Kakšen je graf v računalništvu? Vključuje niz predmetov, ki se imenujejo vertices ali vozlišča, nekateri pa so povezani s tako imenovanimi. Rebra. Na primer, graf na sliki (a) je sestavljen iz štirih vozlišč, ki so označeni z A, B, C in D, od katerih je B povezan z vsako od treh vozlišč z robovi, povezani pa sta tudi C in D. Dva vozlišča sta v bližini, če sta povezana z robom. Na sliki je prikazan tipičen način izdelave grafov v informatiki. Krogi predstavljajo tocke in linije, ki povezujejo vsak par, so rebra.

Kakšen graf se imenuje ne usmerjen v računalništvo? Njegov odnos med obema koncema rebra je simetričen. Reber jih preprosto poveže med seboj. V mnogih primerih pa je treba izraziti asimetrične odnose - na primer dejstvo, da A kaže na B, ne pa obratno. Ta cilj je definicija grafa v računalništvu, ki je še vedno sestavljena iz niza vozlišč skupaj z nizom usmerjenih robov. Vsak usmerjen rob je povezava med vrvmi, katere smer ima vrednost. Usmerjeni grafi so predstavljeni, kot je prikazano na sliki (b), njihovi robovi pa predstavljajo puščice. Ko je potrebno poudariti, da je graf ni usmerjen, ga imenujemo neusmerjeno.

Modeli omrežij

Grafi v računalništvu služijo kot matematični model omrežnih struktur. Naslednja slika prikazuje strukturo interneta, nato pa se imenuje ARPANET, decembra 1970, ko je imela le 13 točk. Vozlišča so računalniška središča, robovi pa povezujejo dve vrvi z neposredno povezavo med njimi. Če ne upoštevate nadgrajenega zemljevida ZDA, ostala slika je grafikon z 13 vozlišči, podoben prejšnjim. V tem primeru je dejanska razporeditev toćk zanemarljiva. Pomembno je, katera vozlišča so medsebojno povezana.

Uporaba grafov v računalništvu vam omogoča, da si predstavljate, kako so stvari fizično ali logično povezane med seboj v omrežni strukturi. 13-vozlišče ARPANET je primer komunikacijskega omrežja, v katerem lahko računalniške točke ali druge naprave prenašajo sporočila, robovi pa so neposredne povezave, preko katerih se lahko prenašajo informacije.

Poti

Čeprav se grafi uporabljajo na številnih različnih področjih, imajo skupne značilnosti. Teorija grafov (računalništva) je morda najpomembnejša - ideja, da se stvari pogosto gibljejo vzdolž robov, ki stalno prehajajo od vozlišča do vozlišča, bodisi da gre za potnika več letov ali informacije, prenesene od osebe do osebe v družabno omrežje ali uporabnika Računalnik, ki sledi povezavam, ki zaporedoma obiščejo več spletnih strani.

Ta ideja motivira opredelitev poti kot zaporedja tock, povezanih z robovi. Včasih je treba upoštevati pot, ki vsebuje ne samo vozlišča, temveč tudi zaporedje robov, ki jih povezujejo. Na primer, zaporedje tock MIT, BBN, RAND, UCLA je pot v grafu interneta ARPANET. Prehod vozlišč in robov se lahko ponovi. Na primer, SRI, STAN, UCLA, SRI, UTAH, MIT so tudi pot. Pot, v kateri se robovi ne ponovijo, se imenuje veriga. Če se vozlišča ne ponovijo, jih imenujemo preprosta veriga.

Cikli

Posebno pomembne vrste grafov v računalništvu so cikli, ki predstavljajo obročno strukturo, kot je zaporedje vozlišč LINC, CASE, CARN, HARV, BBN, MIT, LINC. Poti z vsaj tremi robovi, v katerih sta prva in zadnja vozlišča enaka, drugi pa različni, so ciklični grafi v računalništvu.

Primeri: ciklus SRI, STAN, UCLA, SRI je najkrajši in SRI, STAN, UCLA, RAND, BBN, UTAH, SRI je veliko večji.

Pravzaprav vsak rob grafika ARPANET pripada ciklu. To je bilo storjeno namerno: če katera koli od njih ne uspe, se bo pojavila možnost premikanja od enega vozlišča do drugega. Cikli v komunikacijskih in transportnih sistemih so prisotni, da zagotavljajo redundanco - zagotavljajo alternativne poti po drugačni poti. V družabni mreži pogosto vidimo tudi cikle. Ko na primer ugotovite, da je bližnji šolski prijatelj bratranec vaše žene dejansko delal s svojim bratom, to je cikel, ki ga sestavljajo vas, vaša žena, njen bratranec, njegov šolski prijatelj, njegov zaposleni (to je vaš Brat) in nazadnje, spet vi.

Povezani graf: definicija (informatika)

Naravno je vprašati, ali je mogoče iz vsakega vozlišča pridobiti katero koli drugo vozlišče. Graf je koherenten, če obstaja pot med vsakim parom tock. Na primer, omrežje ARPANET je povezani graf. Enako velja za večino komunikacijskih in prometnih omrežij, saj je njihov cilj usmerjanje prometa iz enega vozlišča na drugega.

Po drugi strani pa ni a priori razloga za pričakovati, da bodo te vrste grafov v računalništvu razširjene. Na primer, v družabni mreži ni težko predstavljati dveh ljudi, ki nista med seboj povezani.

Komponente

Če diagrami v računalniški znanosti niso povezani, potem se naravno razgradijo v niz povezanih fragmentov, skupin vozlišč, ki so izolirani in nepreseki. Na primer, na sliki so prikazani trije deli: prvi - A in B, drugi - C, D in E, tretji pa preostale tocke.

Komponente povezljivosti grafov so podmnožica vozlišč, v katerih:

• Vsako točko podskupine ima pot do katere koli druge;
• Podmnožica ni del večjega sklopa, v katerem ima vsako vozlišče pot do katere koli druge.

Ko so grafiki v računalništvu razdeljeni na njihove komponente, je to le začetni način opisa njihove strukture. V tej komponenti lahko pride do bogate notranje strukture, ki je pomembna za interpretacijo omrežja. Na primer, formalna metoda določanja pomembnosti vozlišča je ugotoviti, koliko delov se graf razdeli, če je vozlišče odstranjeno.

Največja komponenta

Obstaja metoda kvalitativnega ocenjevanja komponent povezljivosti. Na primer, obstaja svetovno socialno omrežje s povezavami med dvema osebama, če sta prijatelja.

Ali je povezana? Verjetno ne. Povezljivost je precej krhka lastnost in obnašanje ene vozlišča (ali majhnega nabora) ga lahko izniči. Na primer, ena oseba brez živih prijateljev bo sestavljena iz ene vertexe, zato graf ni skladen. Ali pa oddaljeni tropski otok, ki ga sestavljajo ljudje, ki nimajo stika z zunanjim svetom, bo tudi majhna komponenta mreže, kar potrjuje njeno neskladnost.

Svetovna mreža prijateljev

Toda nekaj drugega je. Na primer, bralec priljubljene knjige ima prijatelje, ki so odraščali v drugih državah in z njimi sestavljajo eno komponento. Če upoštevate starše teh prijateljev in prijateljev, so vsi ti ljudje tudi v isti komponenti, čeprav nikoli niso slišali za bralca, govorili drug jezik in nikoli niso bili z njim. Torej, medtem ko svetovna mreža prijateljstva ni skladna, bralec vstopi v zelo veliko komponento, ki prodira v vse dele sveta, vključno z ljudmi iz zelo različnih okolij in dejansko vsebuje velik del svetovnega prebivalstva.

Enako velja za nabore omrežnih podatkov - velika, kompleksna omrežja imajo pogosto največjo komponento, ki vključuje pomemben del vseh vozlišč. Poleg tega, ko omrežje vsebuje največjo komponento, je skoraj vedno samo ena. Da bi razumeli, zakaj se moramo vrniti na primer s svetovno mrežo prijateljstva in poskusiti predstavljati prisotnost dveh največjih komponent, od katerih vsaka vključuje milijone ljudi. Zahtevati je treba en rob iz ene od prvih komponent v drugo, tako da se obe največji komponenti združita v eno. Ker je rob edinstven, je v večini primerov neverjetno, da se ne oblikuje in zato dve največji komponenti v realnih omrežjih nikoli ne opazita.

V nekaterih redkih primerih, ko sta dve največji komponenti dolgo časa obstajali v resnični mreži, je bila njihova združitev nepričakovana, dramatična in v končni fazi imela katastrofalne posledice.

Komponenta Fusion Crash

Na primer, po prihodu evropskih raziskovalcev v civilizacijo zahodne poloble, pred približno pol tisočletja, se je zgodila globalna kataklizma. Z omrežnega vidika je bilo videti tako: za pet tisoč let je svetovna socialna mreža verjetno sestavljala dve velikanski komponenti - ena v Severni in Južni Ameriki, druga pa v Evraziji. Iz tega razloga se je tehnologija razvila neodvisno v dveh komponentah in še huje, človeških boleznih itd., Ko so končno prišli v stik, so tehnologije in bolezni ene hitro in katastrofalno napolnile drugo.

Ameriška srednja šola

Koncept maksimalnih komponent je uporaben za sklepanje o omrežjih in v veliko manjših velikostih. Zanimiv primer je grafikon, ki prikazuje romantično razmerje v ameriški srednji šoli v obdobju 18 mesecev. Dejstvo, da vsebuje največjo sestavino, je pomembno, kadar gre za širjenje spolno prenosljivih bolezni, kar je bil namen študije. Učenci so morda imeli v tem času le en partner, vendar so kljub temu, ne da bi to spoznali, bili del najvišje komponente in zato del številnih potencialnih prenosnih poti. Te strukture odražajo razmerja, ki so se morda že zdavnaj končale, vendar so posamezniki povezani v verigah predolgo, da postanejo predmet pozornosti in gossip. Kljub temu so resnične: ker so družbena dejstva nevidna, a logično tekoča makrostruktura, ki je nastala kot produkt posamične mediacije.

Iskanje razdalje in širine

Poleg informacij o tem, ali sta vozlišča povezana z dvema vozliščema, teorija grafov v računalništvu omogoča, da se seznanijo s svojo dolžino - v prometu, komunikaciji ali razširjanju novic in bolezni, pa tudi, ali gre skozi nekaj vrhov ali množico.

Če želite to narediti, določite dolžino poti, ki je enaka številu korakov, ki jih vsebuje od začetka do konca, to je število robov v zaporedju, ki ga naredi. Na primer, pot MIT, BBN, RAND, UCLA ima dolžino 3 in MIT, UTAH je 1. Z uporabo dolžine poti lahko govorimo o tem, ali sta dve vozlišči v grafu blizu drug drugemu ali daleč: razdalja med dvema točkama je dolžina Najkrajša pot med njimi. Na primer, razdalja med LINC in SRI je 3, čeprav se morate prepričati o tem, se prepričajte, da med njimi ni dolžine 1 ali 2.

Algoritem iskanja je širok

Pri majhnih grafih se lahko razdalja med dvema vozliščema enostavno izračuna. Za kompleksne pa je potreben sistematičen način določanja razdalj.

Najbolj naraven način za to in s tem najbolj učinkovito je naslednje (na primeru globalne mreže prijateljev):

• Vsi prijatelji so razglašeni za razdaljo 1.
• Vsi prijatelji prijateljev (brez števila že označenih) so razglašeni, da se nahajajo na razdalji 2.
• Vsi njihovi prijatelji (znova, brez štetja označenih ljudi) se razglasijo za oddaljeno na razdalji 3.

Nadaljevanje na ta način se iskanje izvaja v naslednjih plasti, od katerih je vsaka enota nad prejšnjo. Vsaka nova plast je sestavljena iz vozlišč, ki še niso sodelovali v prejšnjih, in ki vstopajo v rob z vrha prejšnjega sloja.

Ta tehnika se imenuje iskanje po širini, saj v grafu išče izhodno stran od začetnega vozlišča, najprej zajema najbližje. Poleg zagotavljanja načina določanja razdalje lahko služi kot koristna konceptualna osnova za organizacijo strukture grafa, pa tudi kako zgraditi graf v informatiki in postaviti tocke na podlagi njihove razdalje od fiksne izhodišce.

Iskanje po širini se lahko uporablja ne le za mrežo prijateljev, temveč tudi za katerikoli graf.

Svet je majhen

Če se vrnete v svetovno mrežo prijateljev, lahko vidite, da argument, ki pojasnjuje lastništvo največje komponente, dejansko pove nekaj več: ne samo, da ima bralec poti do prijateljev, ki ga povezujejo z velikim deležem svetovnega prebivalstva, vendar pa so te poti presenetljivo kratke .

Ta zamisel je bila imenovana "pojav tesnega sveta": svet se zdi majhen, če razmišljate o tem, kakšna kratka pot povezuje dve osebi.

Teorijo "šestih rokovnikov" je prvič eksperimentalno raziskal Stanley Milgram in njegovi kolegi v šestdesetih letih prejšnjega stoletja. Ni imel podatkov o družabnih omrežjih in s proračunom 680 dolarjev se je odločil preskusiti priljubljeno idejo. V ta namen je prosil 296 naključno izbranih pobudnikov, da pošljejo pismo borznemu posredniku, ki je živel v predmestju Bostona. Pobudnikom so dobili nekaj osebnih podatkov o namenu (vključno z naslovom in poklicu) in morali so poslati pismo osebi, ki jo poznata po imenu, z istimi navodili, da je dosegla cilj čim hitreje. Vsako pismo je prešlo v roke številnih prijateljev in oblikovalo verigo, ki je bila zaprta na borznem posredniku izven Bostona.

Med 64 verigami, ki so dosegle cilj, je bila povprečna dolžina šest, kar je potrdilo število dveh desetletij prej v naslovu predstave John Gare.

Kljub vsem pomanjkljivostim te raziskave je poskus pokazal enega najpomembnejših vidikov našega razumevanja socialnih mrež. V naslednjih letih je naredil širši zaključek: socialna omrežja imajo praviloma zelo kratke poti med samovoljnimi pari ljudi. In čeprav se takšne posredne povezave s poslovnimi voditelji in političnimi voditelji ne izplačujejo dnevno, ima ta kratka pot zelo pomembno vlogo pri hitrostih informacij, bolezni in drugih vrst okužb v družbi ter v možnostih dostopa, ki jih socialna mreža zagotavlja ljudem z Popolnoma nasprotne lastnosti.