Grafikoni u informatici: definicija, vrste, aplikacije, primjeri. Teorija grafova u računalnoj znanosti

Grafikoni u informatici su način definiranja odnosa u kombinaciji elemenata. To su glavni predmeti studija teorija grafova.

Osnovne definicije

Što se sastoji od grafa u računalnoj znanosti? To uključuje skup objekata koji se nazivaju vrhovi ili čvorovi, od kojih su neki povezani s tzv. rebra. Na primjer, grafikon na slici (a) sastoji se od četiri čvora, označena s A, B, C i D, od kojih je B povezan sa svakim od tri vrha po rubovima, a C i D su također povezani. Dva čvora su susjedna ako su spojeni rubom. Slika pokazuje tipičan način izrade grafikona na računarskoj znanosti. Krugovi predstavljaju vrhove, a linije koje povezuju svaki par njih su rebara.

Koji se grafikon naziva ne-orijentiranom u računalnoj znanosti? Njegov odnos između dva kraja rebra je simetričan. Rebro ih jednostavno povezuje jedni s drugima. U mnogim slučajevima, međutim, potrebno je izraziti asimetrične odnose - na primjer, da A označava B, ali ne obratno. Ovaj cilj definira se definicijom grafikona u informatičkoj tehnologiji koja se još sastoji od skupa čvorova, zajedno s skupom orijentiranih rubova. Svaki orijentirani rub je veza između vrhova čiji smjer ima vrijednost. Smjereni grafikoni prikazani su kako je prikazano na slici (b), njihovi rubovi su prikazani strelicama. Kada je potrebno naglasiti da je grafikon ne-usmjeren, on se zove undirected.

Modeli mreža

Grafovi u računalnoj znanosti služe matematički model mrežne strukture. Sljedeća slika prikazuje strukturu Interneta, potom ARPANET, u prosincu 1970, kada je imala samo 13 bodova. Čvorovi su računalni centri, a rubovi povezuju dva vrha s izravnom vezom između njih. Ako ne obraćate pažnju na zemljovid SAD-a koji se preklapaju, ostatak slike je 13-čvorni grafikon sličan prethodnim. U ovom slučaju, stvarni raspored vertica je beznačajan. Važno je da su čvorovi međusobno povezani.

Korištenje grafikona u računalnoj znanosti omogućuje vam zamisliti kako su stvari fizički ili logički povezane jedna s drugom u strukturi mreže. 13-čvor ARPANET je primjer komunikacijske mreže u kojoj top računala ili drugih uređaja mogu slati poruke, a rubovi predstavljaju izravnu vezu na koji se podaci mogu prenijeti.

ruta

Iako se grafikoni upotrebljavaju u različitim područjima, oni imaju zajedničke značajke. teorija grafova (informatika) uključuje možda najvažniji od njih - ideju da stvari često se kreću po rubovima, redom se kreće od čvora do čvora, bilo da je putnik nekoliko letova ili informacije se prenose s osobe na osobu u društvenoj mreži, ili korisnik računalo, slijedno posjećivanje brojnih web stranica, slijedeći veze.

Ova ideja motivira definiranje rute kao slijed vrhova povezanih rubovima. Ponekad postaje neophodno razmotriti put koji ne sadrži samo čvorove, već i redoslijed rubova koji ih povezuju. Na primjer, slijed vrhova MIT, BBN, RAND, UCLA je ruta u internetskom grafikonu ARPANET. Prolaz čvorova i rubova može se ponoviti. Na primjer, SRI, STAN, UCLA, SRI, UTAH, MIT je također ruta. Put u kojem se rubovi ne ponavljaju zove se lanac. Ako se čvorovi ne ponavljaju, to se zove jednostavno lanac.

ciklusa

Posebno važne vrste grafikona u računalnoj znanosti su ciklusi koji predstavljaju strukturu prstena, poput slijeda čvorova LINC, CASE, CARN, HARV, BBN, MIT, LINC. Rute s najmanje tri ruba, u kojima su prvi i zadnji čvorovi isti, a ostali različiti, ciklički su grafikoni u računalnoj znanosti.

Primjeri: ciklus SRI, STAN, UCLA, SRI je najkraći, a SRI, STAN, UCLA, RAND, BBN, UTAH, SRI je mnogo veći.

Zapravo, svaki rub ARPANET grafikona pripada ciklusu. To je učinjeno namjerno: ako bilo koji od njih ne uspije, ostat će mogućnost premještanja iz jednog čvora u drugi. Ciklusi u komunikacijskim i transportnim sustavima prisutni su kako bi osigurali redundanciju - oni pružaju alternativne rute duž različitih putanja. U društvenoj mreži često se vide ciklusi. Kada ste pronašli, na primjer, da je blizak škola prijatelj rođaka svoje žene zapravo radi sa svojim bratom, to je ciklus koji se sastoji od vas, tvoja žena, njezin rođak, njegov prijatelj iz škole, njegov zaposlenik (npr. E. Vaš brat) i, konačno, opet vas.

Povezani grafikon: definicija (informatika)

Prirodno je pitati je li moguće dobiti od svakog čvora do bilo kojeg drugog čvora. Grafikon je koherentan ako postoji ruta između svakog para vrhova. Na primjer, ARPANET mreža je povezani grafikon. Isto se može reći io većini komunikacijskih i transportnih mreža, jer je njihov cilj usmjeravanje prometa s jednog čvora na drugi.

S druge strane, ne postoji a priori razlog za očekivati ​​da su takve grafikone u računalnoj znanosti široko rasprostranjene. Na primjer, u društvenoj mreži nije teško zamisliti dvije osobe koje nisu međusobno povezane.

komponente

Ako je u stupcu nije spojen na računalo, oni, naravno, spadaju u skup povezanih fragmenata, skupina čvorova koji su izdvojeni i ne sijeku. Na primjer, slika prikazuje tri takva dijela: prvi - A i B, drugi - C, D i E, a treći se sastoji od preostalih vrhova.

Komponente povezivanja grafikona su podskup čvorova koji imaju:

• svaki vrh podskupine ima put do bilo kojeg drugog;
• Podskup nije dio većeg skupa u kojem svaki čvor ima put do bilo kojeg drugog.

Kada su grafikoni u računalnoj znanosti podijeljeni u njihove komponente, to je samo početni način opisivanja njihove strukture. Unutar ove komponente može postojati bogata unutarnja struktura koja je važna za tumačenje mreže. Na primjer, formalna metoda određivanja važnosti čvora je odrediti koliko dijelova dijagrami dijele, ako je čvor uklonjen.

Maksimalna komponenta

Postoji metoda kvalitativne procjene komponenata povezivanja. Na primjer, postoji društvena mreža širom svijeta koja ima veze između dvije osobe, ako su prijatelji.

Je li povezana? Vjerojatno ne. Povezanost je prilično osjetljiva svojstva, a ponašanje jednog čvora (ili njihova malena skupina) može poništiti. Na primjer, jedna osoba bez prijatelja uživo bit će komponenta koja se sastoji od jednog vrška, pa se grafikon neće povezati. Ili udaljeni tropski otok, koji se sastoji od ljudi koji nemaju kontakta s vanjskim svijetom, također će biti mala komponenta mreže koja potvrđuje njegovu nesukladnost.

Globalna mreža prijatelja

Ali postoji nešto drugo. Na primjer, čitatelj popularne knjige ima prijatelje koji su odrasli u drugim zemljama i čine s njima jednu komponentu. Ako uzmemo u obzir roditelje tih prijatelja i njihovih prijatelja, svi ti ljudi su u istoj komponenti, iako nikad nije čuo za čitatelja, govori drugi jezik, a uz njega nikada nije bilo. Dakle, iako je globalna mreža prijateljstva - nisu povezani, čitatelj će biti uključeni u komponente su vrlo velike, prodorne u svim dijelovima svijeta, što uključuje i ljude iz različitih sredina i, u stvari, sadrži značajan dio svjetske populacije.

Isto vrijedi i za umrežene skupove podataka - velike, složene mreže često imaju maksimalnu komponentu koja uključuje značajan dio svih čvorova. Štoviše, kada mreža sadrži maksimalnu komponentu, gotovo je uvijek samo jedan. Da bismo razumjeli zašto, moramo se vratiti na primjer globalnom mrežom prijateljstva i pokušati zamisliti prisutnost dviju najvećih komponenti, od kojih svaka uključuje milijune ljudi. To će zahtijevati postojanje jednog ruba iz jedne od prve komponente u drugu, tako da se dvije najveće komponente stapaju u jednu. Budući da je rub jedinstven, u većini slučajeva nevjerojatno je da se ne formira, pa se stoga dvije najveće komponente u stvarnim mrežama nikad ne promatraju.

U nekim rijetkim slučajevima, kada su dvije komponente maksimalna suradnja postoji već dugo vremena u stvarnom mreže, njihov sindikat je neočekivano, dramatičan, i, u konačnici, imati katastrofalne posljedice.

Fusion komponenti

Na primjer, nakon dolaska europskih istraživača u civilizaciju zapadne hemisfere, oko pola tisućljeća, došlo je do globalne kataklizme. S točke gledišta mreže, to izgleda ovako: pet tisuća godina globalne društvene mreže, vjerojatno se sastojao od dvije divovske komponente - jedan u Sjevernoj i Južnoj Americi, a drugi - u Euroaziji. Iz tog razloga, tehnologija je evoluirala nezavisno u dvije komponente, a još gore, kao razvijena i ljudske bolesti, i tako dalje. D. Kad se dvije komponente konačno brzo stupio u kontakt tehnologije i bolesti i katastrofalno preplavljeno drugi.

Američka srednja škola

Koncept maksimalnih komponenti je koristan za razmišljanje o mrežama iu mnogo manjim veličinama. Zanimljiv primjer je grafikon koji ilustrira romantični odnos u američkoj srednjoj školi za 18 mjeseci. Činjenica da sadrži maksimalnu komponentu je važna kada je u pitanju širenje spolno prenosivih bolesti, što je svrha studije. Učenici su možda imali samo jednog partnera za ovo razdoblje, no ipak su to, bez da to shvaćaju, bili dio najveće komponente i stoga dio mnogih potencijalnih transportnih pravaca. Ove strukture odražavaju odnose koji su možda već odavno završeni, ali međusobno povezuju pojedince u lancima da bi postali predmetom pažnje i tračanja. Ipak, oni su stvarni: budući da su društvene činjenice nevidljive, ali logično teče makrostrukture koje su se pojavile kao produkt pojedinačnog posredovanja.

Traženje udaljenosti i širine

Pored informacija o tome jesu li dva čvora povezana put, graf teorija u računalnoj znanosti omogućuje da uče o svojoj dužini - u promet, komunikacije i širenja vijesti i bolesti, kao i da li to ide kroz nekoliko vrhova ili višestruke.

Da biste to učinili, odredite duljinu puta, jednak broju koraka koje sadrži od početka do kraja, tj. Broj rubova u redoslijedu koji ga čini. Na primjer, MIT, BBN, RAND, UCLA put ima dužinu od 3, a MIT, UT - 1. Uporaba duljinu puta, može se reći da, ako su dva čvora raspoređeni u koloni u blizini drugog ili daljini između dva pika definirana je kao duljina najkraći put između njih. Na primjer, udaljenost između LINC-a i SRI-a iznosi 3, iako biste se uvjerili u to, trebali biste provjeriti ne postoji duljina koja je jednaka 1 ili 2 između njih.

Algoritam pretraživanja širine

Za male grafikone, udaljenost između dva čvora može se lako izračunati. No, za složene, postoji potreba za sustavnim načinom određivanja udaljenosti.

Najprirodniji način da se to učini i, stoga, najučinkovitiji jest sljedeći (na primjeru globalne mreže prijatelja):

• Svi se prijatelji prijavljuju na udaljenosti od 1.
• Svi prijatelji prijatelja (ne uključujući one koji su već označeni) proglašeni su na udaljenosti od 2.
• Svi njihovi prijatelji (opet, ne računajući označene ljude) proglašeni su udaljeni s udaljenosti od 3.

Nastavljajući tako, pretraživanje se provodi u kasnijim slojevima, od kojih je svaka jedna jedinica iznad prethodne. Svaki novi sloj sastoji se od čvorova koji još nisu sudjelovali u prethodnim, a koji ulaze u rub s vrha prethodnog sloja.

Ova tehnika se zove širinu prvo pretraživanje, kao i ona traži kolone iz početne čvor, prvenstveno pokriva sljedeća. Osim što pruža metodu za određivanje udaljenosti, to može poslužiti kao koristan konceptualni okvir za organizaciju strukture grafa kao i kako izgraditi graf računala, s pikovima na temelju njihove udaljenosti od fiksnu početnu točku.

Pretraživanje u širini može se primijeniti ne samo na mrežu prijatelja, već na bilo koji grafikon.

Svijet je mali

Ako se vratite na globalnu mrežu prijatelja, možete vidjeti da je argument koji objašnjava pripadnost maksimalne komponente stvarno odobrava nešto više: ne samo da čitatelj ima staze s prijateljima, ga povezuje sa značajnim udjelom svjetske populacije, ali ti putevi su iznenađujuće kratko ,

Ta je ideja nazvana "fenomenom bliskog svijeta": svijet se čini malenim, ako razmišljate o tome koja kratka ruta povezuje bilo koju dvije osobe.

Teoriju "šest prstiju" eksperimentalno je istraživalo Stanley Milgram i njegovi kolege 1960-ih. Bez ikakvih skupova podataka o društvenim mrežama i proračunom od 680 dolara odlučio je provjeriti popularnu ideju. U tu je svrhu pitao 296 slučajno odabranih pokretača da pokušaju poslati pismo burzovaru koji je živio u predgrađu Bostona. Inicijatori su dobili neke osobne informacije o svrsi (uključujući adresu i zanimanje) i oni su morali proslijediti pismo osobi koju su poznavali po imenu, uz iste upute da je što je brže dostigao cilj. Svako je pismo prošlo kroz ruke brojnih prijatelja i formiralo lanac koji je zatvorio mjenjačnicu izvan Bostona.

Među 64 lanaca koji su dosegli cilj, prosječna dužina imao šest godina, što potvrđuje broj navedena dva desetljeća ranije u play Ivan Gera naslov.

Unatoč svim nedostacima ove studije, eksperiment je pokazao jedan od najvažnijih aspekata našeg razumijevanja društvenih mreža. U narednim godinama, on je napravio širi zaključak: društvene mreže, u pravilu, imaju vrlo kratke putove između proizvoljnih parova ljudi. A čak i ako se takve posredne veze s poslovnim čelnicima i političkim liderima ne platiti za sebe na dnevnoj bazi, postojanje takvih kratkih puteva igra veliku ulogu u brzini širenja informacija, bolesti i drugih vrsta infekcije u zajednici, kao i pristupne prilike koje socijalna mreža pruža ljudi s potpuno suprotne kvalitete.