Mi az átjárható gráf a gráfelméletben?

A gráfelmélet kontextusában a bejárható gráf olyan gráf, amelyben az összes csúcsot és élt be lehet járni. Más szóval, ez egy gráf, amely lehetővé teszi, hogy minden csúcsot pontosan egyszer meglátogassunk, és visszatérjünk a kezdő csúcshoz.

A bejárható gráfot összekapcsolt gráfnak is nevezik, mivel ez egy olyan gráf, amelyben az összes csúcs össze van kapcsolva .

Vegyünk például egy egyszerű gráfot három csúcsú A, B és C, ahol van egy él A és B között, egy él B és C között, és egy él A és C között. Ez a gráf bejárható, mert Kezdje az A csúcstól, kövesse az éleket B-be, majd C-be, és térjen vissza A-hoz.

Másrészt egy olyan gráf, amely két szétválasztott összetevőt tartalmaz, például két külön gráfot, nem járható be, mert nem lehet minden csúcsot meglátogatni. pontosan egyszer, és térjünk vissza a kiinduló csúcsra.