1 of 7

IN2010 Gruppe 4

Uke 8

2 of 7

Mer om grafer

2-sammenhengende grafer

Sterkt sammenhengende komponenter

3 of 7

2-sammenhengende grafer

En graf er 2-sammenhengende hvis:

Det finnes minst to stier fra enhver node til enhver annen node, hvor disse stiene ikke deler noen kanter eller noder (unntatt start og slutt)

Altså - man kan alltid finne en vei fra enhver node til enhver annen node, om man fjerner én vilkårlig node fra grafen.

4 of 7

2-sammenhengende grafer

Hvis det finnes en node, som er slik at grafen ikke lenger er sammenhengende hvis man fjerner den, er det en separasjonsnode.

En node med grad 1 kan ikke være en separasjonsnode.

Alle noder i et tre, som ikke er løvnoder, er separasjonsnoder.

5 of 7

6 of 7

Sterkt sammenhengende komponenter

En sterkt sammenhengende komponent er en delgraf, hvor alle noder kan nå hverandre. Denne må være maksimal - altså må vi inkludere alle noder vi kan inkludere i komponenten.

Sterkt sammenhengende komponenter vil ikke endre seg om man reverserer grafen (bytter retning på alle kanter)

7 of 7