Bir Euler döngüsü ile bir Hamilton döngüsü arasındaki fark nedir?

Bir Euler devresi her kenarı tam olarak bir kez kullanırken, bir Hamilton döngüsü her köşeyi tam olarak bir kez ziyaret etmektedir; ilkinin basit bir derece karakterizasyonu varken, ikincisine karar vermek hesaplama açısından zordur.

Bir grafiğin k-bağlantılı olması ne anlama gelmektedir?

Bir graf, k'den daha az köşe çıkarıldığında bağlantılı kalıyorsa k-bağlantılıdır; bu durum, grafiğin köşe arızalarına karşı direncini nicel olarak belirtmektedir.

Graf Temelleri ve Bağlantılılık

Graf teorisinin temelleri, grafikleri, temel parametrelerini ve bir grafiğin nasıl bir arada durduğunu açıklayan bağlantılılık ve geçiş kavramlarını tanıtmaktadır.

PaperMind ile konu bulYakındaMakale ve konu bul

Tools & resources

Slaytları indir

Learn & explore

VideoYakında

Tanım

Bir graf, bir dizi köşeden (vertices) ve köşe çiftlerini birleştiren bir dizi kenardan (edges) oluşmaktadır; bağlantılılık, köşeler veya kenarlar çıkarıldığında grafiğin tek parça halinde kalma derecesini ölçmektedir.

Kapsam

Bu konu, grafiklerin ve yönlü grafiklerin (digraphs) tanımlarını, dereceyi ve el sıkışma lemmasını, alt grafikleri ve izomorfizmi, yürüyüşleri, yolları ve döngüleri, bağlantılılığı ve bileşenleri ile Euler ve Hamilton grafiklerinin klasik karakterizasyonlarını kapsamaktadır. Graf teorisi boyunca kullanılan terminolojiyi ve temel yapısal sonuçları ortaya koymaktadır.

Temel sorular

Bir grafiğin temel parametreleri - mertebe (order), boyut (size) ve derece (degree) - nelerdir?
Bir graf ne zaman bağlantılıdır ve bağlantılılığı silmelere karşı ne kadar sağlamdır?
Bir graf, her kenarı tam olarak bir kez kullanan kapalı bir yürüyüşü ne zaman kabul eder?
Yollar ve döngüler erişilebilirliği ve yapıyı nasıl kodlar?

Anahtar kavramlar

Köşeler (Vertices), kenarlar (edges) ve derece
Yürüyüşler, yollar ve döngüler
Bağlantılı bileşenler
Köşe ve kenar bağlantılılığı
Euler devreleri
Hamilton döngüleri

Temel kuramlar

El sıkışma lemmasi: Herhangi bir grafikte, tüm köşe derecelerinin toplamı kenar sayısının iki katına eşittir; bu da tek dereceli köşe sayısının çift olduğunu doğrudan ima etmektedir.
Euler devreleri üzerine Euler teoremi: Bağlantılı bir graf, her kenarı tam olarak bir kez geçen kapalı bir yürüyüşe ancak ve ancak her köşenin derecesi çift ise sahiptir; bu sonuç, Euler'in Königsberg köprüleri çözümünün temelini oluşturmaktadır.

Klinik önem

Bağlantılılık analizi, ağ güvenilirliği, yönlendirme ve hataya dayanıklı iletişim ve ulaşım sistemlerinin tasarımında merkezi bir rol oynamaktadır; Euler ve Hamilton yapıları ise yönlendirme ve sıralama problemlerinde ortaya çıkmaktadır.

Tarihçe

Euler'in 1736 tarihli Königsberg makalesi graf geçişini tanıtmıştır; Menger'in 1927 tarihli teoremi ise modern teoriyi temel alan bağlantılılık ve ayrık yollar arasındaki kurucu ikiliği ortaya koymuştur.

Öne çıkan isimler

Leonhard Euler
Karl Menger

İlgili konular

Temel eserler

diestel2017

Sıkça sorulan sorular

Bir Euler döngüsü ile bir Hamilton döngüsü arasındaki fark nedir?: Bir Euler devresi her kenarı tam olarak bir kez kullanırken, bir Hamilton döngüsü her köşeyi tam olarak bir kez ziyaret etmektedir; ilkinin basit bir derece karakterizasyonu varken, ikincisine karar vermek hesaplama açısından zordur.
Bir grafiğin k-bağlantılı olması ne anlama gelmektedir?: Bir graf, k'den daha az köşe çıkarıldığında bağlantılı kalıyorsa k-bağlantılıdır; bu durum, grafiğin köşe arızalarına karşı direncini nicel olarak belirtmektedir.