Какво е обходим граф в теорията на графите?

В контекста на теорията на графите, обходим граф е график, в който е възможно да се обходят всички върхове и ръбове. С други думи, това е граф, който ни позволява да посетим всеки връх точно веднъж и да се върнем към началния връх.

Проходимият граф е известен също като свързан граф, тъй като това е граф, в който всички върхове са свързани един с друг .

Например, разгледайте проста графика с три върха A, B и C, където има ребро между A и B, ребро между B и C и ребро между A и C. Този график е проходим, защото можем започнете от връх A, следвайте ръбовете до B и след това до C и се върнете към A.

От друга страна, графика с два несвързани компонента, като например два отделни графа, не е проходима, защото не е възможно да се посети всеки връх точно веднъж и се върнете към началния връх.