Çizgelerde Hamilton Çevrimi ve Yolunun Tespiti İçin Kenar Etkinliğine Dayalı Yeni Bir Algoritma
Fırat Üniversitesi Mühendislik Bilimleri Dergisi, cilt.38, sa.2, ss.435-450, 2026 (TRDizin)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 38 Sayı: 2
- Basım Tarihi: 2026
- Doi Numarası: 10.35234/fumbd.1926890
- Dergi Adı: Fırat Üniversitesi Mühendislik Bilimleri Dergisi
- Derginin Tarandığı İndeksler: TR DİZİN (ULAKBİM)
- Sayfa Sayıları: ss.435-450
- İnönü Üniversitesi Adresli: Evet
Özet
Bir çizgede tüm düğümleri birbirine bağlayan Hamilton çevrimi ve Hamilton yolunun varlığını araştırmak NP-tam bir problemdir. Bu makalede, kenar ağırlıkları olmayan keyfi bir çizgede Hamilton çevrimini oluşturmak için E2 Algoritması önerilmektedir. Öncelikle, temel kesitleri elde etmek amacıyla özel örten ağaçlar olan Kmax ve Kmin oluşturulmaktadır. Daha sonra, kenar etkinliğini belirlemek için her bir kenarın toplam temel kesit sayısı elde edilmektedir. Ardından, en etkin kenar üzerindeki en yüksek dereceli düğümden başlayarak önceliği belirleyen bir yöntemle tüm düğümler dolaşılmaktadır. Böylece, açgözlü geçiş başarılı olduğunda, tüm düğümler arasında bir Hamilton döngüsü veya yol oluşturulur. E² geri izleme içermeyen deterministik bir açgözlü algoritma olduğundan, her Hamilton grafiğinde bir Hamilton döngüsü bulmayı garanti etmez; ancak her zaman polinom zamanında sonlanır. Bu çalışmada, Hamilton çevrimini elde etmek için bu yöntemler ilk kez kullanılmaktadır. Ayrıca, üstel algoritma karmaşıklığının ortaya çıkmasını önlemek amacıyla nesne yönelimli bir yapı sunulmaktadır. Son olarak, yöntemin doğruluğunu göstermek için bazı genel çizgelerin önerilen yöntem kullanılarak Hamiltonyen olup olmadığı gösterilmektedir.
Searching for the existence of a Hamiltonian cycle and path connecting all nodes in a graph is an NP-complete problem. This article proposes the E2 Algorithm for constructing the Hamiltonian cycle in an arbitrary graph without edges’ weights. The Kmax and Kmin that are particular spanning trees are generated first to obtain the fundamental cuts. Then, each edge's total number in the fundamental cuts is obtained to state edge efficiency. Next, all nodes are navigated with a method that determines priority, starting with the highest degree node at the most efficient edge. Thus, when the greedy traversal succeeds, a Hamiltonian cycle or path is constructed between all nodes. Since E² is a deterministic greedy algorithm without backtracking, it does not guarantee finding a Hamiltonian cycle in every Hamiltonian graph; however, it always terminates in polynomial time. These methods are used for the first time to obtain the Hamiltonian cycle in this study. In addition, we present an object-oriented construction to avoid getting exponential algorithm complexity. Finally, to prove the correctness of the method, we show whether some general graphs are Hamiltonian using the proposed method.