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 , och att denna graf är mycket, mycket, stor .

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:

Länkarna mellan atomer i molekyler och kristallgaller bildar en graf.

Spridningen av sjukdomar och epidemier kan modelleras med hjälp av ett nätverk.

I biologi bildar de evolutionära träden som visar arternas ursprung en graf.

De olika komponenterna i elektriska kretsar och datorchips bildar ett nätverk.

Den grammatiska strukturen för språk kan modelleras med hjälp av grafer, till exempel för att skapa översättningsalgoritmer.

Grafer har också många tillämpningar inom sannolikhet , spelteori och finansiell matematik .

Ändra språk

Logga in på Mathigon

Dela med sig

Återställ framsteg

Ordlista

Grafer och nätverkGrafer i vardagen

Sociala nätverk