Mikä on läpikäytävä graafi graafiteoriassa?

Graafiteorian kontekstissa läpikäytävä graafi on graafi, jossa on mahdollista kulkea kaikki kärjet ja reunat. Toisin sanoen se on graafi, jonka avulla voimme vierailla jokaisessa kärjessä täsmälleen kerran ja palata aloituspisteeseen.

Käitettävä graafi tunnetaan myös yhdistettynä graafina, koska se on graafi, jossa kaikki kärjet ovat yhteydessä toisiinsa .

Otetaan esimerkiksi yksinkertainen graafi, jossa on kolme kärkeä A, B ja C, jossa on reuna A:n ja B:n välillä, reuna B:n ja C:n välillä ja reuna A:n ja C:n välillä. Tämä graafi on läpikäytävissä, koska voimme aloita kärjestä A, seuraa reunoja B:hen ja sitten C:hen ja palaa A.

Toisaalta graafi, jossa on kaksi erillistä komponenttia, kuten kaksi erillistä kuvaajaa, ei ole läpikäytävä, koska jokaisessa kärjessä ei ole mahdollista käydä täsmälleen kerran ja palaa alkupisteeseen.