Grafi v informatiki: 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 študija teorija grafov.

Osnovne definicije

Kaj sestavlja grafa iz računalništva? Vključuje niz predmetov, ki se imenujejo vertices ali vozlišča, nekateri pa so povezani s tako imenovanimi. rebra. Na primer, diagram na sliki (a) je sestavljen iz štirih vozlišč, označena A, B, C in D, katerih B je povezan z vsako od drugih treh reber tock, in C in D so povezani tudi. Dva vozlišča sta v bližini, če sta povezana z robom. Na sliki je prikazan tipičen način izdelave grafov na področju računalništva. 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. Rebro preprosto jih povezuje med seboj. V mnogih primerih pa je treba izraziti asimetrične odnose, na primer, da A kaže na B, ne pa obratno. Ta cilj je opredeljen z definicijo grafike v informatiki, ki še vedno sestoji iz niza vozlišč, skupaj z nizom usmerjenih robov. Vsak usmerjen rob je povezava med vertikami, katere smer ima vrednost. Usmerjeni grafi so prikazani, kot je prikazano na sliki (b), njihovi robovi pa predstavljajo puščice. Ko je potrebno poudariti, da je graf ni usmerjen, se imenuje neusmerjen.

Modeli omrežij

Grafi v računalništvu služijo matematični model omrežne strukture. 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 tocki 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 v fizični ali logični povezavi med seboj povezane strukture omrežja. 13-vozlišče ARPANET je primer komunikacijskega omrežja, v katerem se lahko vrh računalniki ali druge naprave pošiljajo sporočila in robovi predstavljajo neposredno povezavo, na 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štvo) vključuje morda najpomembnejše od njih - ideja, da se stvari pogosto premikajo vzdolž robov, zaporedno gibljejo od vozlišča do vozlišča, se je potnik pred nekaj leti ali informacije prenašajo s človeka na človeka v socialne mreže, ali uporabnik računalnika, 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 internetnem grafu 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, se imenujejo preprosta veriga.

Cikli

Posebno pomembna vrsta v računalniških grafih - it ciklov, ki predstavljajo obročno strukturo, kot zaporedje vozlišč LINC, Case, CARN, HARV, BBN, MIT, LINC. Poti z vsaj tremi rebri, pri kateri sta prva in zadnja vozlišče enaka ter ostale pa različna, predstavljata ciklični grafi iz računalništva.

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

Pravzaprav vsak rob ARPANETnega grafa pripada ciklu. To je bilo storjeno namerno, če kateri od njih ne uspe, bo možnost prehoda iz enega vozlišča do drugega. Cikli v komunikacijskih in transportnih sistemov so navzoči odpuščanja - zagotavljajo alternativne poti za druge kolesarske poti. V družabni mreži pogosto vidimo tudi cikle. Ko boste našli, na primer, da je v bližini šola prijatelj bratranca ženi dejansko deluje s svojim bratom, da je cikel, ki je sestavljen iz vas, vaša žena, njen bratranec, njegov prijatelj iz šole, njegova zaposlenih (npr. E. Vaš brat) in, končno, 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 povezan 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 razloga, da pričakujemo, 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 povezani drug z drugim.

Komponente

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

Komponente povezljivosti grafov so podmnožica vozlišč, ki imajo:

• vsaka veriga podskupine ima pot do katere koli druge;
• Podmnožica ni del večjega niza, 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 okviru te komponente je lahko bogata notranja struktura, pomembna za interpretacijo omrežja. Na primer, formalni način določanja vozlišče pomembno je, da se ugotovi, koliko delov bo razdeljen število, če se odstrani vozlišče.

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 povezan. Ali pa oddaljeni tropski otok, sestavljen iz ljudi, ki nima stika z zunanjim svetom, bo tudi majhen del mreže, kar potrjuje njeno neskladnost.

Globalna mreža prijateljev

Toda nekaj drugega je. Na primer, bralec popularne knjige ima prijatelje, ki so zrasli v drugih državah, in jih naredi eno komponento. Če upoštevamo starše teh prijateljev in njihovih prijateljev, vsi ti ljudje so tudi v isti komponenti, čeprav še nikoli niso slišali za bralca, govorijo drug jezik, in poleg nje še nikoli ni bilo. Torej, čeprav je globalna mreža prijateljstva - ni povezan, bralec bo vključena v komponente so zelo velike, prodira v vse dele sveta, ki vključuje ljudi iz različnih okolij in dejansko vsebuje velik delež svetovnega prebivalstva.

Enako velja za omrežne nabore podatkov - velika, zapletena 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 z globalno mrežo prijateljstva in poskusiti predstavljati prisotnost dveh največjih komponent, od katerih vsaka vključuje milijone ljudi. Zahtevati bo, da bo edini 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, zato se nikoli ne upoštevata dva največja sestavna dela v realnih omrežjih.

V nekaterih redkih primerih, ko sta se obe komponenti največja sodelovanje obstaja že dolgo časa v realnem omrežju, je bila njuna zveza nepričakovano, dramatično, in, končno, imajo katastrofalne posledice.

Fuzija komponent

Na primer, po prihodu evropskih raziskovalcev v civilizaciji na zahodni polobli približno pol tisočletja nazaj, je bila svetovna katastrofa. Z vidika omrežja, je bilo videti takole: pet tisoč let globalne socialne mreže, najverjetneje sestavljen iz dveh velikan komponente - eden v Severni in Južni Ameriki, in drugi - v Evraziji. Iz tega razloga se je tehnologija razvijala samostojno v dveh komponent, in, še huje, kot se je razvil in človeških bolezni, in tako naprej. D. Ko obe komponenti končno dobil na dotik tehnologije in bolezni hitro in pogubno overflowed drugi.

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, ko gre za širjenje spolno prenosljivih bolezni, kar je bil namen študije. Učenci so morda imeli v tem času le en partner, vendar kljub temu, ne da bi to spoznali, so bili del najvišje komponente in zato del mnogih možnih oddajnih poti. Te strukture odražajo razmerja, ki so se morda že zdavnaj končala, vendar so predolgo povezani posamezniki v verigah, da postanejo predmet pozornosti in gossip. Kljub temu so resnični: kot družbena dejstva so nevidna, toda logično tekoča makrostruktura, ki je nastala kot produkt posamične mediacije.

Iskanje razdalje in širine

Poleg informacij o tem, ali sta dve vozlišči povezani pot, teorija grafov v računalništvu vam omogoča, da spoznajo svoje dolžine - v transport, komunikacije ali širjenje novic in bolezni, kot tudi, ali gre skozi več vrhov ali večkratnik.

Če želite to narediti, določite dolžino poti, enako število korakov, ki jih vsebuje od začetka do konca, tj. E. število robov v zaporedju, ki je. Na primer, MIT, BBN, RAND, UCLA pot ima dolžino 3, in MIT, UTAH - 1. Z dolžino poti, lahko rečemo, da če sta dve vozlišči razporejeni v stolpcu blizu drug drugemu ali daleč razdalje med dvema vrhovoma je definirana kot dolžina najkrajša pot med njimi. Na primer, razdaljo med LINC in SRI 3, čeprav bi zagotovili to, je treba preveriti odsotnost dolžino enako 1 ali 2, med njima.

Algoritem iskanja po širini

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 primer globalne mreže prijateljev):

• Vsi prijatelji so razglašeni za razdaljo 1.
• Vsi prijatelji prijateljev (razen tistih, ki so že označeni) so prijavljeni, 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 zgornjim delom 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 tega, da omogoča določitev razdalje, lahko služi kot koristna konceptualna osnova za organizacijo strukture grafikona, kot tudi za gradnjo grafa v informatiki, ki postavlja vertices na podlagi njihove razdalje od fiksne začetne točke.

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

Svet je majhen

Če greš nazaj v globalno mrežo prijateljev, lahko vidite, da je trditev, ki pojasnjuje, spada v največjo komponento res odobril nekaj več: ne samo bralec ima poti k prijateljem, ga povezuje z znatnim deležem svetovnega prebivalstva, vendar te poti so presenetljivo kratek .

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

Teorija "šestih rokovnikov" je prvič eksperimentalno raziskala Stanley Milgram in njegovi kolegi v šestdesetih letih prejšnjega stoletja. Ker ni imel nobenih podatkov o družabnih omrežjih in s proračunom 680 dolarjev, se je odločil, da preveri popularno idejo. V ta namen je prosil 296 naključno izbranih pobudnikov, da bi poskušali poslati pismo borznemu posredniku, ki je živel v predmestju Bostona. Pobudniki so imele nekatere osebne podatke o namenu (vključno z naslovom in stroke), in so morali poslati pismo, v katerem oseba, ki so poznali po imenu, z istimi navodili, tako da se čim hitreje doseže cilj. Vsako pismo je prešlo v roke številnih prijateljev in oblikovalo verigo, ki je bila zaprta na borznem posredniku zunaj Bostona.

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

Kljub vsem pomanjkljivostim te študije 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 tudi, če te posredne povezave s poslovnimi voditelji in politični voditelji ne plačajo sami dnevno, obstoj takšnih kratkih progah igra veliko vlogo pri hitrosti razširjanja informacij, bolezni in druge vrste okužb v skupnosti, kot tudi dostop do možnosti, da socialne mreže zagotavlja ljudem z popolnoma nasprotne lastnosti.