DOI: 10.6084/m9.figshare.29958116
title: Graf Teorisi Eğitiminde Yeni Bir Araç: Z3 ve Keçeci Yerleşimi ile Hamilton Probleminin İnteraktif Keşfi

description: Graf teorisi, bilgisayar bilimleri ve matematik eğitiminin temel taşlarından birini oluşturmakla birlikte, Hamilton döngüsü gibi NP-tam problemlerin soyut doğası, öğrenciler için önemli bir anlama zorluğu teşkil etmektedir. Bu tür problemlerin sezgisel olarak kavranması, genellikle karmaşık ve standart dışı graf yapılarının analitik olarak incelenmesini gerektirir. Geleneksel öğretim metotları, bu karmaşıklığı etkili bir şekilde aktarmada yetersiz kalabilmekte ve öğrencilerin konuya olan ilgisini azaltabilmektedir. Bu çalışmada, söz konusu pedagojik zorluklara yanıt olarak, Hamilton döngüsü probleminin keşfi ve analizi için tasarlanmış yeni bir birleşik hesaplamalı ve görsel bir araç sunulmaktadır. Geliştirilen bu çerçeve, iki temel teknolojiyi bir araya getirmektedir: Microsoft Research tarafından geliştirilen yüksek performanslı bir SMT çözücüsü olan Z3 (Z3-Solver) ve tarafımızca geliştirilen, sıralı yapılar için optimize edilmiş yenilikçi bir graf yerleşim algoritması olan Keçeci Dizilimi (Layout). Yaklaşımımızın temelinde, Hamilton döngüsü problemini algoritmik bir çözüm arayışından ziyâde bir dizi mantıksal kısıtın tatmin edilmesi problemi olarak yeniden formüle etmek yatmaktadır. Bu bildirimsel model, Z3 çözücüsüne sunularak bir grafın Hamilton döngüsü içerip içermediği otomatik olarak kanıtlanmaktadır. Bu yöntem, geleneksel deneme-yanılma veya kaba kuvvet (brute-force) algoritmalarına kıyasla hem daha verimli hem de sonucun doğruluğunu matematiksel olarak garanti eden bir yapı sunar. Z3, bir çözüm bulduğunda (SAT), bu çözümü temsil eden bir model üretir; çözüm olmadığında ise (UNSAT), döngünün var olmadığını kesin olarak bildirir. Çalışmanın eğitime yönelik asıl yeniliği ise Z3 tarafından elde edilen bu soyut mantıksal sonuçların görselleştirilmesi aşamasında ortaya çıkmaktadır. Standart graf yerleşim algoritmaları (örn. Fruchterman-Reingold), genellikle estetik açıdan optimize edilmiş olsalar da sıralı bir yolun veya döngünün takibini zorlaştırabilen karmaşık ve öngörülemez çıktılar üretirler. Buna karşın, önerdiğimiz Keçeci Dizilimi, düğümleri ana bir eksen boyunca sıralı bir zikzak deseniyle konumlandırarak grafın içsel yol yapısını net bir şekilde ortaya koyar. Z3'ün bulduğu Hamilton döngüsü bu düzen üzerine vurgulandığında, öğrenciler döngünün grafın tamamını nasıl kat ettiğini, her düğüme tam olarak bir kez nasıl uğradığını ve başlangıç noktasına nasıl döndüğünü adım adım ve sezgisel olarak takip edebilirler. Bu görsel netlik, Dodekahedral graf (Hamiltonian) ve Herschel graf (Hamiltonian olmayan) gibi klasik örnekler üzerinde test edilmiş ve kanıtlanmıştır. Sonuç olarak, bu bütünleşmiş araç, NP-tam problemler gibi zorlu konuların öğretiminde soyut mantık ile somut görsel kanıt arasında bir köprü kurarak, öğrenci anlama ve katılımını artırma potansiyeline sahip güçlü bir pedagojik kaynak olarak öne çıkmaktadır.<br><b>Keywords:</b>Hamilton Döngüsü, Z3 Teorem Kanıtlayıcısı, Z3-Solver, Z3, SMT Çözücü, SMT Solver, Kısıt Memnuniyet Problemi, CSP, Graf Teorisi, Graf Yerleşim Algoritmaları, Keçeci Dizilimi, Keçeci Yerleşimi, Keçeci Layout, NP-Tam Problemler, Hesaplamalı Mantık, Otomatik Akıl Yürütme, Veri Görselleştirme.