Çizge Kuramı
Çizge kuramı, köşelerin kenarlarla birleştiği yapılar olan çizgeleri, ikili ilişkilerin ve ağların matematiksel modelleri olarak incelemektedir.
Tanım
Her biri bir çift köşeyi birleştiren bir kenar kümesiyle birlikte bir köşe kümesi olan çizgelerin ve bu bağlantıların yapısı altında değişmez olan özelliklerin matematiksel olarak incelenmesidir.
Kapsam
Bu alan, çizgelerin yapısını, özelliklerini ve parametrelerini (bağlantılılık, yollar ve döngüler, ağaçlar, düzlemsellik, renklendirmeler, eşleşmeler ve akışlar) ile çizge özelliklerinin birbirini nasıl kısıtladığına dair ekstremal ve olasılıksal soruları kapsamaktadır. Ayrık matematiğin merkezinde yer almakta ve bilgisayar bilimi, yöneylem araştırması ile doğa ve sosyal bilimlerdeki ağlar için bir dil sağlamaktadır.
Alt konular
Temel sorular
- Bir çizgenin bağlantılılığından, derece dizisinden veya döngü yapısından hangi yapısal özellikler türetilebilir?
- Bir çizge ne zaman düzlemde kesişmeden çizilebilir veya az sayıda renkle renklendirilebilir?
- Belirli bir alt yapıyı önlerken bir çizge ne kadar büyük veya yoğun olabilir?
- Yollar, eşleşmeler ve akışlar bir ağ üzerinde optimizasyonu nasıl mümkün kılar?
Anahtar kavramlar
- Köşeler, kenarlar ve derece
- Bağlantılılık ve bileşenler
- Yollar, döngüler ve ağaçlar
- Düzlemsellik
- Çizge renklendirme
- Eşleşmeler ve akışlar
Klinik önem
Çizgeler, iletişim ve ulaşım ağlarını, sosyal ve biyolojik etkileşim ağlarını, devre ve bağımlılık yapılarını ve çizelgeleme problemlerini modellemektedir; bu da çizge kuramını bilgisayar bilimi ve yöneylem araştırmasında temel bir araç haline getirmektedir.
Tarihçe
Çizge kuramının kökenleri, Euler'in 1736'da Königsberg köprüleri problemine getirdiği çözüme dayanmaktadır ve 20. yüzyılda renklendirme, bağlantılılık ile Erdos, Tutte ve diğerlerinin olasılıksal ve yapısal yöntemleri üzerine yapılan çalışmalarla olgunlaşmıştır.
Öne çıkan isimler
- Leonhard Euler
- William Tutte
- Bela Bollobas
İlgili konular
Temel eserler
- diestel2017
- bollobas1998
Sıkça sorulan sorular
- Bir çizge ile bir ağ arasındaki fark nedir?
- Bir çizge, köşeler ve kenarlardan oluşan soyut matematiksel bir nesnedir; bir ağ ise genellikle ağırlıklar, kapasiteler veya yönler gibi ek verilerle donatılmış, gerçek bir sistemi modelleyen bir çizgeyi ifade etmektedir.
- Königsberg köprüleri problemi neden önemliydi?
- Euler'in yedi köprünün her birinden tam olarak bir kez geçilemeyeceğini kanıtlaması, problemi köşeler ve kenarlar düzeyine soyutlayarak çizge kuramının ve topolojinin temelini atmıştır.