Hamilton yolu problemi

Hamilton yolu problemi, Hamilton yolunun çözümü ile ilgili problemdir.

İspat: Yönsüz graflarda Hamilton yolunun bulunması NP-tamdır (NP-complete)

Hamilton Yolu (Hamiltonian Path):
• Bir graftaki her düğümden (node) tam 1 kere geçilmelidir.
• Bir kere geçilen kenardan (edge) bir daha geçilmemelidir.

İspatta indirgeme (reduction) metodu kullanılacaktır.

Teorem : Yönlü graflarda Hamilton yolunun bulunması NP-tamdır. (İspatlanmış kabul ediliyor.)
Bu teoremdeki yönlü grafı şu şekilde tanımlayabiliriz:
HAMPATH = { <G,s,t> | G, s den t ye bir Hamilton yolu bulunan yönlü bir graftır.}
G grafını, düğümleri s' ve t' olan bir yönsüz G' grafına indirgeyeceğiz.

İspatlanacak Teorem:
G, s den t ye Hamilton yolu bulunan bir graftır <=> G', s' den t' ye Hamilton yolu bulunan bir graftır.
G' yi şöyle tanımlayabiliriz:
• G deki her u düğümü (s ve t hariç), G' de uⁱⁿ, u^mid ve u^out düğümleri ile yer değiştirilir.
• G' deki s ve t düğümleri, G' de s^out ve tⁱⁿ düğümleri ile yer değiştirilir.
• G' deki kenarlar 2 şekilde oluşturulur:
1. uⁱⁿ, u^mid ve u^out, sırayla birbiriyle bağlıdır.
2. Eğer G de bir kenar u dan v ye gidiyorsa, G' de u^out ve vⁱⁿ birbiriyle bağlı gösterilir.

İspatlanacak Teorem şu şekilde değiştirilir:
G, s den t ye Hamilton yolu bulunan bir graftır <=> G', s^out tan tⁱⁿ e Hamilton yolu bulunan bir graftır.

1. Kısım ispatı:
G, s den t ye Hamilton yolu bulunan bir graftır <= G', s^out tan tⁱⁿ e Hamilton yolu bulunan bir graftır.

G grafının P Hamilton yolu bulunan düğümleri :
P : s, u₁, u₂, ..., u_k, t

G' grafının P' Hamilton yolu bulunan düğümleri :
P' : s^out, u₁ⁱⁿ, u₁^mid, u₁^out, u₂ⁱⁿ, u₂^mid, u₂^out, ..., tⁱⁿ

2. Kısım ispatı:
G, s den t ye Hamilton yolu bulunan bir graftır => G', s^out tan tⁱⁿ e Hamilton yolu bulunan bir graftır.
Sol tarafın doğru olduğunu kabul ediyoruz. Yani G', s^out tan tⁱⁿ e üçlü düğümlerden üçlü düğümlere giden bir P' Hamilton yolu bulunan bir graf olduğunu iddia ediyoruz. Yukarıda tanımladığımız gibi s^out başlangıç düğümünden başlayarak iddiamızı ispatlayabiliriz. s^out tan sonraki düğüm u_iⁱⁿ (herhangi bir i için) olmak zorunda. Tanım gereği sonraki düğümler sırasıyla u_i^mid ve u_i^out olmak zorundadır. Bir sonraki düğüm tanım gereği u_jⁱⁿ (herhangi bir j için)olmak zorundadır. Bu yol tⁱⁿ e ulaşana kadar aynı mantıkla devam edeceği için iddia ispatlanmış olur.

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Matematik</span> nicelik, yapı, uzay ve değişim gibi konularla ilgilenen bilim dalı

Matematik ; sayılar, felsefe, uzay ve fizik gibi konularla ilgilenir. Matematikçiler ve filozoflar arasında matematiğin kesin kapsamı ve tanımı konusunda görüş ayrılığı vardır.

<span class="mw-page-title-main">Çizge teorisi</span> nesneler arasındaki ikili ilişkileri modellemek için kullanılan matematiksel yapılar olan grafiklerin incelenmesi

Graf teorisi, çizge teorisi veya çizit teorisi, grafları inceleyen matematik dalıdır. Graf, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Bir graf, çizge veya çizit, düğümlerden (köşeler) ve bu düğümleri birbirine bağlayan kenarlardan oluşur.

<span class="mw-page-title-main">Termodinamik</span> enerji bilimi

Termodinamik; ısı, iş, sıcaklık ve enerji arasındaki ilişki ile ilgilenen bilim dalıdır. Basit bir ifadeyle termodinamik, enerjinin bir yerden başka bir yere ve bir biçimden başka bir biçime transferi ile ilgilenir. Bu süreçteki anahtar kavram, ısının, belirli bir mekanik işe denk gelen bir enerji biçimi olmasıdır.

Nen karar problemlerini içeren karmaşıklık sınıfıdır.

Lenfatik sistem veya lenfoid sistem, omurgalılarda dolaşım sistemi ve bağışıklık sistemi'nin bir parçası olan bir organ sistemi'dir. Geniş bir lenf ağından, lenfatik damarlardan, lenf düğümlerinden, lenfatik veya lenfoid organlardan ve lenfoid dokulardan oluşur. Damarlar lenf adlı berrak bir sıvıyı kalbe doğru taşır.

Open Systems Interconnection (OSI) modeli ISO tarafından geliştirilmiştir. Bu modelle, ağ farkındalığına sahip cihazlarda çalışan uygulamaların birbirleriyle nasıl iletişim kuracakları tanımlanır.

Lenf düğümü, lenf nodu veya lenf bezi, lenfatik sistemin ve adaptif bağışıklık sistemi'nin böbrek şeklinde bir ikincil lenfoid organ'ıdır.

SAT problemi bir NP-tam sınıfı problemidir.

Hamilton Yolu, yönlü veya yönsüz bir grafta Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir.

3SAT ve KLIK problemleri, Turing makinasından polinom zamanda kararlaştırılabilen NP problemleri arasında yer alır. Bu problemlerin birbirinin cinsine çevrilmesine indirgeme denilir.

Köşe Örtme, bir çizge (graf) içerisindeki tüm kenarların en az sayıda seçilebilecek düğüm ile kapsanabilir olup olmadığının bulunması problemidir. Bu problemin NP sınıfı içerisinde olduğu bilinmektedir. Amaç, bu problemin NP-Tam sınıfında olup olmadığının ispatıdır.

Bilgisayar bilimlerinde, alt küme toplamı problemi karmaşıklık kuramında ve kriptografide önemli yeri olan bir problemdir.

Arama algoritmaları, bilgisayar biliminde seçili özelliklere göre istenilen bilgileri bulan algoritmalardır. Listeler, metinler ve şekiller üzerinde çalışırlar.

18. yy. ve sonrasında geliştirilmiş, genellikle vektörel mekanik olarak nitelendirilen ve orijinalinde Newton mekaniği olarak bilinen analitik mekanik, klasik mekaniğin matematiksel fizik kaynaklarıdır. Model harekete göre analitik mekanik, Newton’un vektörel enerjisinin yerine, hareketin iki skaler özelliği olan kinetik enerjiyi ve potansiyel enerjiyi kullanır. Bir vektör, yön ve nicelik ile temsil edilirken bir skaler, nicelik ile(yoğunluğu belirtirken) temsil edilir. Özellikle Lagrange mekaniği ve Hamilton mekaniği gibi analitik mekanik de, sorunları çözmek için bir sistemin kısıtlamalarının ve tamamlayıcı yollarının kavramını kullanarak klasik mekaniğin kullanım alanını etkili bir şekilde yapılandırır. Schrödinger, Dirac, Heisenberg ve Feynman gibi kuram fizikçileri bu kavramları kullanarak kuantum fiziğini ve onun alt başlığı olan kuantum alan teorisini geliştirdiler. Uygulamalar ve eklemelerle, Einstein’a ait kaos teorisine ve izafiyet teorisine ulaşmışlardır. Analitik mekaniğin çok bilindik bir sonucu, modern teorik fiziğin çoğunu kaplayan Noether teoremidir.

Bir petri ağı sistemlerin incelenmesi için kullanılabilecek bir araçtır. Petri ağları, sistemin matematiksel bir modelle modellenebilmesine izin verir. Bir Petri ağı, geçiş ve yerleşim düğümlerinden oluşan tek yönlü iki parçalı graf olarak da tanımlanabilir. Ok şeklinde gösterilen yönlü eğriler, bir geçişten önce ve sonra hangi yerlerin olduğunu tanımlarlar.

<span class="mw-page-title-main">İki parçalı graf</span>

Graf teorisinde, düğümleri her kenar iki kümede de birer bitiş ucuna sahip olacak şekilde iki ayrı kümeye ayrılabilen graflara iki parçalı graf adı verilir.

Matematikte graf ya da çizge, nesne çiftlerinin bir anlamda "ilişkili" olduğu bir dizi nesne kümesini belirleyen bir yapıdır. Nesneler, köşeler adı verilen matematiksel soyutlamalara karşılık gelir ve ilgili düğüm çiftlerinin her birine bir kenar, ayrıt adı verilir. Tipik olarak bir graf, kenarları için çizgiler veya eğriler ile birleştirilen, düğümler için bir nokta veya daire kümesi olarak diyagram şeklinde gösterilir. Graflar ayrık matematikte çalışmanın amaçlarından biridir.

<span class="mw-page-title-main">Yönlü çizge</span> yönlendirilmiş kenarlara sahip grafik

Çizge teorisinde, yönlü çizge düğümler ve hepsi birer yöne sahip kenarlardan oluşan çizgedir.

<span class="mw-page-title-main">Bézout teoremi</span> aciklama

Bézout teoremi, cebirsel geometride $n$ değişkenli $n$ polinomun ortak sıfırlarının sayısı ile ilgili bir ifadedir. Orijinal biçiminde teorem, genel olarak ortak sıfırların sayısının, polinomların derecelerinin çarpımına eşit olduğunu belirtir. Adını Fransız matematikçi Étienne Bézout'dan almıştır.

Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.