grafalgoritmer gjennomgang

Hva er en graf?

En graf er en samling av noder (eller hjørner) og kanter som forbinder disse nodene. Den representerer relasjoner mellom objekter.

Noder vs. Kanter

Noder: punkter i grafen. Kanter: forbindelser mellom noder. - Noder representerer objekter. - Kanter representerer relasjoner.

Definer en rettet graf.

En rettet graf har kanter med en spesifikk retning, fra en node til en annen. Retningen angir forholdet mellom nodene.

Fyll ut: En graf med ingen kanter er en ____.

En graf med ingen kanter er en 'isolert graf'.

Er en komplett graf alltid koblet?

Sant. En komplett graf har en kant mellom hver par av noder, dermed er den alltid sammenkoblet.

Forklar en koblet graf.

En koblet graf er en graf der det finnes en sti mellom ethvert par av noder. Hvis noen noder ikke er forbundet, er grafen ikke koblet.

Hva er en vekting i grafteori?

En vekting er en verdi som tilordnes til en kant i en graf, ofte brukt til å representere kostnader eller avstander.

Definer en urettet graf.

En urettet graf har kanter uten retning. Forbindelsen mellom noder er symmetrisk, det vil si at hvis A er koblet til B, så er også B koblet til A.

Hva er en undergraf?

En undergraf er en graf som er dannet ved å ta et utvalg av noder og kanter fra en større graf. Den beholder strukturen til den opprinnelige grafen.

Forklar begrepet grad i grafteori.

Graden av en node er antallet kanter som er koblet til den. I en rettet graf skiller vi mellom inn-grad og ut-grad.

Hva er en syklus i en graf?

En syklus er en sti i grafen som begynner og slutter i samme node, og hvor ingen andre noder gjentas.

Er en graf med 5 noder og 4 kanter alltid koblet?

Ikke nødvendigvis. En graf kan ha færre enn n-1 kanter og likevel være ikke-koblet.

DFS (Dybde-først søk) → hva gjør det?

DFS traverserer dypere i en graf før det går tilbake. Det besøker en node, og deretter rekurserer til den første nabonoden inntil det ikke er flere uutforskede noder.

BFS (Bredde-først søk) vs DFS?

BFS utforsker noder på samme nivå før det går dypere, mens DFS går dypere før det backtracker. BFS gir korteste vei i uvektede grafer, mens DFS ikke garanterer dette.

Kurtzalgoritmen → hva brukes den til?

Kurtzalgoritmen brukes til å finne den korteste veien fra en kilde til alle noder i en vektet graf med ikke-negative vekter.

Er Dijkstra’s algoritme alltid korrekt?

Ja, Dijkstra’s algoritme er korrekt for grafer med ikke-negative vekter, men den fungerer ikke med negative vekter.

Fill in the blank: Prim’s algoritme brukes til ____ .

Prim’s algoritme brukes til å finne minimal spanning tree (MST) i en vektet graf.

A*-algoritmen vs Dijkstra’s algoritme?

A*-algoritmen legger til en heuristisk komponent som hjelper i søket, og gir ofte raskere resultater enn Dijkstra’s algoritme.

Grafrepresentasjon: matrise vs liste?

Inngangsmatrise krever O(V^2) plass, mens nabonodeliste krever O(E + V) plass. Liste er mer effektiv for sparse grafer.

Bellman-Ford algoritme → hva gjør den?

Bellman-Ford finner korteste vei fra en kilde til alle noder, også i grafer med negative vekter, men uten negative sykluser.

Er det sant at DFS kan brukes til topologisk sortering?

Ja, DFS kan brukes til topologisk sortering av en aktsyklist graf ved å lagre noder i en stakk.

Hva er en aktsyklist graf?

En aktsyklist graf er en graf uten sykluser. Den kan inneholde rettede eller urettede kanter, men har ingen sirkler.

Fordeler med BFS?

BFS finner korteste vei i uvektede grafer, oppdager nivåer av noder, og er enkel å implementere ved bruk av kø.

Kruskal's algoritme → hva finner den?

Kruskal's algoritme finner Minimum Spanning Tree (MST) ved å bruke en sortert liste av kanter og en union-find datastruktur.

Hvorfor brukes heuristikker i A*-algoritmen?

Heuristikker brukes i A*-algoritmen for å estimere den gjenstående kostnaden, noe som kan redusere søketid og informere neste valg.

Hva er en syklus i en graf?

En syklus er en sti i en graf som starter og slutter ved samme node uten å besøke noen noder mer enn én gang.

Tidskompleksitet av Dijkstra's algoritme med prioritetskø?

Tidskompleksiteten av Dijkstra's algoritme er O((E + V) imes ext{log} V) når den implementeres med en prioritetskø.

Forbindelse mellom grafer og nettverk?

Grafer brukes til å representere nettverk, hvor noder er punkter og kanter representerer forbindelser eller relasjoner.

Transportnettverk →

Grafalgoritmer brukes til optimalisering av ruter for transport, som i logistikk for å finne den korteste veien mellom lagre og kunder.

Spillteori →

Grafalgoritmer kan modellere strategiske interaksjoner mellom spillere i konkurranse- eller samarbeidsspill.

Sosiale nettverk →

Kan brukes til å analysere forbindelser mellom brukere, finne innflytelsesrike personer og optimalisere innholdsspredning.

Hvorfor er Dijkstra's algoritme viktig?

Den finner den korteste stien i et grafisk nettverk, essensielt for navigasjonsapper og ruteplanlegging.

Sanntidsruting →

Bruker grafalgoritmer for å tilpasse ruter basert på sanntidsdata om trafikk og hendelser.

Er Kruskal's algoritme alltid optimal?

True. Den gir alltid minimum kostnad for å forbinde noder i en graf uten sykluser.

Fyll ut: Grafalgoritmer kan brukes i ________ for å analysere transportnettverk.

logistikk

Søkning i graf →

BFS og DFS er grafalgoritmer for å utforske noder, viktige for oppgaveløsning og AI.

Anvendelser av minimum spanning tree? →

Brukes i nettverksdesign, som å legge kabler eller rørledninger med minimal kostnad. Eksempler: Kruskal's, Prim's.

True or False: Grafalgoritmer brukes ikke i dataspill.

False. Grafalgoritmer er essensielle for AI-bevegelse og kartdesign.

Optimalisering av ressurser →

Grafalgoritmer kan minimere kostnader og maksimere effektivitet i ressursfordeling og prosjektledelse.

Hva brukes A* algoritmen til?

Den brukes i navigasjon og søk, da den kombinerer Dijkstra's metode med heuristisk informasjon for raskere resultater.