Grafer och nätverkGrafer i vardagen
Vi har sett många olika tillämpningar av grafteori i de föregående kapitlen, även om vissa av dem var lite motstridiga. Det visar sig dock att grafer är grunden för många objekt, begrepp och processer i vardagen.
Internet är till exempel en stor, virtuell graf. Varje toppunkt är en enskild webbsida och varje kant innebär att det finns en hyperlänk mellan två sidor. Observera att länkar bara går en väg, så den här grafen är
Vissa webbplatser, som Wikipedia eller Facebook, har massor av inkommande länkar, medan många mindre webbplatser kan ha mycket få inkommande länkar. Detta är det underliggande konceptet som Google använder för att sortera sökresultat.
Webbplatser med fler inkommande länkar tenderar att vara av högre kvalitet och bör visas högst upp i sökresultaten. När du till exempel söker efter "London" visas officiella turistinformationssidor före små butiker i London eller bloggar om människor som bor i London. Denna enkla idé från grafteori, Page Rank Algoritmen , gjorde Google betydligt bättre än andra tidiga sökmotorer.
Internet är det största nätverket som någonsin skapats av mänskligheten. Den här bilden visar en mycket liten andel av alla servrar som är anslutna till Internet:
Medan webbplatser och hyperlänkar bildar en virtuell graf, finns det också det fysiska nätverket av datorer, servrar, routrar, telefonlinjer och kablar.
Varje gång du ringer eller laddar en webbplats måste nätoperatörer hitta ett sätt att ansluta avsändare och mottagare, utan att överskrida kapaciteten för någon enskild kabel eller anslutning. Grafteori och sannolikhet gör det möjligt att garantera en tillförlitlig tjänst, till exempel genom att hitta avledningar när en viss anslutning är upptagen.
Grafer spelar också en viktig roll i transport och navigering. Alla flyg-, tåg- och tunnelbana nätverk bildar diagram som kan användas när du skapar effektiva scheman. En av de mest kända graferna är London Underground-kartan:
Alla vägar och motorvägar bildar också ett stort nätverk, som används av navigeringstjänster som Google Maps när man arbetar med den kortaste vägen mellan två givna punkter.
I framtiden kommer intelligenta transportsystem att minska trafikstockningar och olyckor genom att dirigera bilar mer effektivt genom att använda platsdata som samlas in från smartphones och självkörande bilar. Detta kan spara miljoner timmar förlorade på vägen varje år, minska föroreningar avsevärt och låta räddningstjänsterna resa snabbare.
Den här bilden visar nätverket av kommersiella flygbolag över norra Europa.
Det finns otaliga andra grafer i vetenskap, teknik eller vardagsliv:
Sociala nätverk
Låt oss slutligen tänka på ett särskilt bra exempel på diagram som finns i vardagen: sociala medier. Här representerar vertikaler
När vi ritar diagram på sociala medier kan vi se vissa kluster av ömsesidiga vänner, som kan ha gått på samma skola eller bo i samma stad. Vi kan också bestämma människors centralitet , vilket beror på hur välkopplad en toppunkt är, och som kan vara ett mått på en persons popularitet på sociala medier.
2014 hade Facebook 1,4 miljarder aktiva användare och totalt mer än 200 miljarder vänskap. Hälften av alla Facebook-användare har mer än 200 vänner, och eftersom de flesta av våra vänner har ett liknande antal vänner, kan vi lätt ha tiotusentals vänner av vänner .
En spännande fråga skulle nu vara: om du väljer två slumpmässiga Facebook-användare, hur många "vänskapskanter" skulle du behöva följa för att komma från det ena till det andra? Till exempel är avståndet mellan vänner
2016 genomförde Facebook en studie för att avgöra hur dess användare är anslutna till varandra. De fann att du i genomsnitt är ansluten till någon annan på Facebook via högst 3,57 andra personer. Och detta inkluderar kändisar, politiker eller till och med kungligheter!
Med andra ord, om du väljer någon av miljarder Facebook-användare över hela världen kommer de förmodligen att ha en vän till en vän som känner en vän till en av dina vänner. Vi säger att det finns 3,57 graders separering .
1929, när den ungerska författaren
1967 genomförde
Idag är var och en av oss en del av otaliga osynliga grafer som ligger till grund för våra sociala interaktioner, resor, Internet och teknik, vetenskap och så mycket mer.