Grafik Teorisinde Geçilebilir Grafik Nedir?

Grafik teorisi bağlamında, geçilebilir bir grafik, tüm köşelerin ve kenarların geçilmesinin mümkün olduğu bir grafiktir. Başka bir deyişle, her köşeyi tam olarak bir kez ziyaret etmemizi ve başlangıç köşesine dönmemizi sağlayan bir grafiktir. .

Örneğin, A, B ve C olmak üzere üç köşesi olan ve A ile B arasında bir kenar, B ile C arasında bir kenar ve A ile C arasında bir kenar bulunan basit bir grafik düşünün. Bu grafik geçilebilir çünkü şunları yapabiliriz: A köşesinden başlayın, B'ye ve ardından C'ye kadar olan kenarları takip edin ve A'ya dönün.

Öte yandan, iki ayrı grafik gibi birbiriyle bağlantısız iki bileşene sahip bir grafik, her köşeyi ziyaret etmek mümkün olmadığından geçilemez. tam olarak bir kez ve başlangıç köşesine dönün.