กราฟข้ามผ่านในทฤษฎีกราฟคืออะไร?

ในบริบทของทฤษฎีกราฟ กราฟเคลื่อนที่ได้คือกราฟที่สามารถเคลื่อนที่ผ่านจุดยอดและขอบทั้งหมดได้ กล่าวอีกนัยหนึ่ง มันเป็นกราฟที่ช่วยให้เราสามารถเยี่ยมชมทุกจุดยอดได้เพียงครั้งเดียวและกลับไปยังจุดยอดเริ่มต้น กราฟที่เคลื่อนที่ได้เรียกอีกอย่างว่ากราฟที่เชื่อมต่อกัน เนื่องจากเป็นกราฟที่จุดยอดทั้งหมดเชื่อมต่อถึงกัน .

ตัวอย่างเช่น พิจารณากราฟง่ายๆ ที่มีจุดยอด A, B และ C สามจุด โดยมีขอบระหว่าง A และ B ขอบระหว่าง B และ C และขอบระหว่าง A และ C กราฟนี้สามารถข้ามผ่านได้เพราะเราสามารถ เริ่มต้นที่จุดยอด A เดินตามขอบไปยัง B จากนั้นไปที่ C และกลับไปที่ A.

ในทางกลับกัน กราฟที่มีองค์ประกอบสองส่วนที่ไม่เชื่อมต่อกัน เช่น กราฟสองกราฟที่แยกจากกัน จะไม่สามารถเดินทางข้ามได้เนื่องจากไม่สามารถไปที่ทุกจุดยอดได้ เพียงครั้งเดียวและกลับสู่จุดยอดเริ่มต้น