Riječnik

Odaberite jednu od ključnih riječi s lijeve strane ...

Grafikoni i mrežeGrafovi u svakodnevnom životu

Vrijeme čitanja: ~15 min
Ova je stranica automatski prevedena i može sadržavati pogreške. Javite nam se ako nam želite pomoći u pregledu prijevoda!

Vidjeli smo mnogo različitih primjena teorije grafova u prethodnim poglavljima, mada su neke od njih bile pomalo zamišljene. Ispada, međutim, da su grafovi sami temelj mnogih predmeta, koncepata i procesa u svakodnevnom životu.

Na primjer, Internet je ogroman, virtualni graf. Svaka vršica pojedinačna je web stranica, a svaki rub znači da postoji hiperveza između dvije stranice. Imajte na umu da veze idu samo u jednom smjeru, tako da je ovaj grafikon i da je ovaj grafikon vrlo, vrlo velik.

Neke web stranice, poput Wikipedije ili Facebooka, imaju puno dolaznih veza, dok mnoge manje web stranice mogu imati vrlo malo dolaznih veza. To je temeljni koncept koji Google koristi za razvrstavanje rezultata pretraživanja.

Web stranice s više dolaznih veza obično su kvalitetnije i trebaju biti prikazane na vrhu rezultata pretraživanja. Na primjer, kada tražite "London", službene informacije o turističkim informacijama prikazuju se pred malim trgovinama u Londonu ili blogovima ljudi koji žive u Londonu. Ova jednostavna ideja iz teorije grafova, algoritam rangiranja stranica, učinila je Google znatno boljim od ostalih pretraživača.

Internet je najveća mreža koju je čovječanstvo ikad stvorilo. Ova slika prikazuje vrlo mali udio svih poslužitelja povezanih na Internet:

© LyonLabs, LLC and Barrett Lyon, 2014

Dok web stranice i hiperveze čine virtualni graf, postoji i fizička mreža računala, poslužitelja, usmjerivača, telefonskih linija i kablova.

Svaki put kad telefonirate ili učitate web mjesto, mrežni operatori moraju pronaći način za povezivanje pošiljatelja i primatelja, bez prekoračenja kapaciteta bilo kojeg pojedinačnog kabela ili veze. Teorija grafova i vjerojatnost omogućuju jamčenje pouzdane usluge, na primjer, pronalaženjem preusmjeravanja kada je određena veza zauzeta.

Grafovi također igraju važnu ulogu u prijevozu i plovidbi. Sve mreže letova, vlaka i podzemne željeznice formiraju grafikone koji se mogu koristiti pri kreiranju učinkovitih voznih linija. Jedan od najprepoznatljivijih grafova je mapa londonskog podzemlja:

Sve ceste i autoceste također čine veliku mrežu koja se koristi za navigacijske usluge poput Google Maps prilikom izrade najkraće rute između dviju zadatih točaka.

U budućnosti će Inteligentni transportni sustavi smanjiti zagušenja i nezgode učinkovitijim usmjeravanjem automobila koristeći podatke o lokaciji prikupljene sa pametnih telefona i automobila koji se voze. Ovo bi moglo uštedjeti milijune sati izgubljenih na cesti svake godine, značajno smanjiti zagađenje i omogućiti hitnim službama da brže putuju.

Ova slika prikazuje mrežu komercijalnih avionskih letova kroz sjevernu Europu.

Postoji bezbroj drugih grafova iz znanosti, inženjerstva ili svakodnevnog života:

Veze između atoma u molekuli i kristalne rešetke tvore graf.

širenje bolesti i epidemija može se modelirati pomoću mreže.

U biologiji, evolucijska stabla koja prikazuju porijeklo vrsta iz grafa.

Različite komponente električnih krugova i računalni čipovi tvore mrežu.

Gramatička struktura jezika može se modelirati pomoću grafikona, na primjer za stvaranje algoritama za prijevod.

Grafovi također imaju mnogo primjena u vjerojatnosti, teoriji igara i financijskoj matematici.

Društvene mreže

Za kraj, razmislimo o jednom posebno dobrom primjeru grafova koji postoje u svakodnevnom životu: društvenim medijima. Ovdje vrhovi predstavljaju , a rubovi predstavljaju prijateljstva, lajkove, pretplate ili sljedbenike.

Kad crtamo grafikone na društvenim mrežama, mogli bismo vidjeti određene nakupine zajedničkih prijatelja, koji su možda išli u istu školu ili žive u istom gradu. Također možemo odrediti središnju povezanost ljudi, što ovisi o dobroj povezanosti i koja može biti mjerilo popularnosti osobe na društvenim mrežama.

  1. godine Facebook je imao 1,4 milijarde aktivnih korisnika i ukupno više od 200 milijardi prijateljstava. Polovina svih korisnika Facebooka ima više od 200 prijatelja, a budući da većina naših prijatelja ima sličan broj prijatelja, lako bismo mogli imati desetke tisuća prijatelja.

Uzbudljivo bi pitanje postalo: ako odaberete bilo kojeg drugog nasumičnog korisnika Facebooka, koliko biste „rubova prijateljstva“ trebali pratiti da biste prešli s jednog na drugog? Na primjer, udaljenost između prijatelja je , udaljenost između prijatelja prijatelja , i tako dalje.

  1. godine Facebook je proveo istraživanje kako bi utvrdio na koji su način njegovi korisnici povezani jedni s drugima. Otkrili su da ste u prosjeku na bilo kome drugom na Facebooku povezani s najviše 3,57 drugih ljudi. A to uključuje slavne, političare ili čak kraljevske!

Drugim riječima, ako odaberete nekog od milijardi korisnika Facebooka širom svijeta, vjerojatno će imati prijatelja prijatelja koji poznaje prijatelja jednog od vaših prijatelja. Kažemo da postoje 3,57 stupnjeva razdvojenosti.

Geographic visualisation of all Facebook friendships in 2010.

  1. godine, kada je mađarska autorica Frigyes Karinthy prvi put predložila ideju o „šest stupnjeva razdvojenosti“, nije postojao Internet niti društveni mediji, već je svijet već počeo postajati sve više povezan.

  2. Stanley Milgram izveo je prvi empirijski eksperiment u kojem je od 296 sudionika koji žive u Nebraski i Kansasu zatraženo da dostave pismo određenoj osobi koja živi u Bostonu, Massachusetts. Svi su morali odabrati prijatelja kojem će poslati pismo, koji je potom odabrao drugog prijatelja. Na svakom koraku pismo se približavalo Bostonu. Milgram je otkrio da u prosjeku ima samo 5,2 posrednika & # 8211; 5,2 stupnja odvajanja.

Danas je svatko od nas dio bezbrojnih nevidljivih grafova koji su temelj naših društvenih interakcija, putovanja, interneta i tehnologije, znanosti i još mnogo toga.

Archie