Grafegenskaper Flashcards
Hva består en graf av?
To mengder:
- V, en mengde med noder
- E, en mengde med kanter
Hva er en sti?
En sekvens av noder i grafen forbundet av kanter, der ingen node gjentas.
Hva er en vei?
En sekvens av noder i grafen forbundet av kanter, der ingen kanter gjentas.
Hva er en sykel?
En sti i en graf med minst tre noder, som forbinder første og siste node.
Hva vil det si om en graf er asyklisk?
Grafen inneholder ingen sykler.
Hva er summen av alle gradene til alle nodene?
deg(v1) + deg(v2) + … + deg(v3) = 2|E|
- Altså summen av gradene til nodene er det dobbelte av antall kanter.
Hva er en komplett graf?
En graf med en kant mellom hvert par av noder.
Hver node er nabo med enhver annen node.
Hvor mange kanter har en komplett graf?
(|V| * (|V| - 1)) / 2
Av dette vet vi at |E| er i O(|V|^2)
Hva er forholdet mellom kanter og noder?
Gitt antall noder så kan vi si hvor mange kanter det maksimalt er.
Antall kanter er altså begrenset av antall noder, men ikke motsatt.
Hva er fordelen med nabo-matrise?
Bra for rettede, tette grafer.
Finne eksisterende og legge til nye kanter tar O(1) tid.
Ulempe:
- Tar stor plass, O(|V|^2)
- Legge til ny node tar O(|V|^2) pga. kopiere hele liste til nytt større array.
Hva er fordelene med nabo-liste?
Velegnet for tynne grafer. Tar O(|V| + |E|) plass.
Hva er en k-sammenhengende graf?
En sammenhengende graf hvor grafen forblir sammenhengende om færre enn k noder blir fjernet.
Hva er en sammenhengende graf?
En graf er sammenhengende hvis det finnes en sti mellom hvert par av noder.
Hva er en sterkt sammenhengende graf og hva slags grafer gjelder uttrykket for?
En rettet graf(!) er sterkt sammenhengende hvis det finnes en sti mellom alle par av noder.
Merk at dette brukes for grafer som er rettede (med retning på kantene).
En retted graf kan være svakt sammehengende, for eksempel om det bare finnes en sti fra a -> b , men ikke en sti tilbake fra b -> a.
Hva er en rettet graf?
En graf der kantene har en retning.
