Vad är en övergångsbar graf i grafteori?

I grafteorisammanhang är en korsningsbar graf en graf där det är möjligt att korsa alla hörn och kanter. Med andra ord, det är en graf som gör att vi kan besöka varje hörn exakt en gång och återgå till startpunkten.

En korsningsbar graf är också känd som en sammankopplad graf, eftersom det är en graf där alla hörn är kopplade till varandra .

Betrakta till exempel en enkel graf med tre hörn A, B och C, där det finns en kant mellan A och B, en kant mellan B och C och en kant mellan A och C. Den här grafen är korsbar eftersom vi kan börja vid toppunkt A, följ kanterna till B och sedan till C, och återvänd till A.

Å andra sidan är en graf med två frånkopplade komponenter, såsom två separata grafer, inte genomkörbar eftersom det inte är möjligt att besöka varje vertex exakt en gång och återgå till startpunkten.