Hva er en gjennomførbar graf i grafteori?

I sammenheng med grafteori er en traverserbar graf en graf der det er mulig å krysse alle toppunktene og kantene. Det er med andre ord en graf som lar oss besøke hvert toppunkt nøyaktig én gang og gå tilbake til startpunktet.

En traverserbar graf er også kjent som en koblet graf, fordi det er en graf der alle toppunktene er koblet til hverandre .

Tenk for eksempel en enkel graf med tre toppunkter A, B og C, der det er en kant mellom A og B, en kant mellom B og C og en kant mellom A og C. Denne grafen kan krysses fordi vi kan start ved toppunkt A, følg kantene til B og deretter til C, og gå tilbake til A.

På den annen side er en graf med to frakoblede komponenter, for eksempel to separate grafer, ikke gjennomkjørbar fordi det ikke er mulig å besøke hvert toppunkt nøyaktig én gang og gå tilbake til startpunktet.