Hvad er en gennemførbar graf i grafteori?

I forbindelse med grafteori er en gennemkørbar graf en graf, hvor det er muligt at krydse alle spidser og kanter. Det er med andre ord en graf, der giver os mulighed for at besøge hvert knudepunkt pr
cis én gang og vende tilbage til starthjørnet.

En gennemkørbar graf er også kendt som en forbundet graf, fordi det er en graf, hvor alle knudepunkter er forbundet med hinanden .

Betragt f.eks. en simpel graf med tre spidser A, B og C, hvor der er en kant mellem A og B, en kant mellem B og C og en kant mellem A og C. Denne graf kan krydses, fordi vi kan start ved toppunkt A, følg kanterne til B og derefter til C, og vend tilbage til A.

På den anden side er en graf med to adskilte komponenter, såsom to separate grafer, ikke gennemkørbar, fordi det ikke er muligt at besøge alle toppunkter pr
cis én gang og vende tilbage til startpunktet.