Graflar Kuramı Nedir?

**Prof. Dr. Sinsi** · 12-19-2012

XVIII

yy?da Euler?in çalışmaları sonucunda ortaya çıkan graflar kuramı, XX

yy?ın başında König ve Kuratowski?nin, Cayley?in ve daha yakınlarda Berge, Erdös ve Harray?nin çalışmalarıyla bir matematik dalı haline geldi

Bilgisayar alanında ve özellikle algoritmalar üzerinde yapılan araştırmalar, graflar kuramına yeni bir soluk getirdi

Graflar kuramı, çok çeşitli uygulamalar için oluşturulan problemleri, noktalar ve noktalar arası bağlantılar yardımıyla çizilen konfigürasyonlara indirgeyerek çözme olanağı verir

GRAFLAR KURAMI
Graflar kuramının, << Königsberg (bugün Rusya?da Kaliningrad) Köprüleri>> denilen probleme kadar dayandığı kabul edilir 1736?da Euler?in çözdüğü bulmacaya benzer bir problem olan << Königsberg Köprüleri >> problemi, şöyle ifade edilebilir: kentin herhangi bir yerinden yola çıkıp, kentteki yedi köprüden yalnızca bir kez geçerek başlangıç noktasına geri dönmek mümkün müdür?
Graflar kuramı, her şeyden önce çözümü aranan bir problemi ya da işi en etkin şekilde temsil edebilmeye ve düzenlemeye yarar Bu problem graf biçimine çevrildikten sonra, tüm amaçları yerine getirecek en hızlı veya en az masraflı yolu bulmak için sistematik yöntemler aranır
Graflardan çok değişik uygulama alanlarında yararlanılır: ulaşım ağlarının optimizasyonunda (yol ya da bilgi ulaşımı), elektrik şebekeleri kavramında, haberleşme ağlarında, istatistiksel mekanikte, kimyasal formüllerde, bilgisayar kuramında, toplumsal bilimlerde, coğrafyada, mimarlıkta?

GRAF NEDİR?

Graf sözcüğünü ilk kez 1822?de İngiliz matematikçi J

J

Sylvester kullandı, gaflar kuramı üzerine ilk kitabı ise 1936?da D

König yayımladı

Garf, bir noktalar(köşeler) kümesi ile bu noktaların arasındaki çizgiler ya da oklar(ayrıtlar) kümesi tarafından tanımlanan bir geometrik çizimdir

Her ayrıtın ucunda gerektiğinde birbiri üzerine gelebilen iki köşe vardır

Eğer grafın her ayrıtında bir başlangıç ve bir sonuç ucu ayırt ediliyorsa, bu graf yönlü olarak tanımlanır

Grafların özellikleri farklı tipten problemleri niteler:

- Eğer bir grafta, iki ayrı köşe tek bir ayrıtla birbirine bağlanıyorsa buna yalın graf denir
- Eğer bir grafta iki ayrı köşe bir dizi kesintisiz ayrıtla birbirine bağlanıyorsa, buna bağlantılı graf denir
Bir << ağaç >> kapalı yol içermeyen bağlantılı bir graftır Ağaçların ya da ağaç görünümlü grafların kullanılmasının örneklerine, veri tabanlarının yönetiminde rastlanır Bilgilerin nasıl düzenlendiğini izleyerek ağacı tanımak, onların incelenmesini kolaylaştırır ve optimize eder Bilgisayarlardaki buna koşut yapı amaçları ve hedefleri düzene koyan bir yöntem izlenerek gerçekleştirilir Bu alan, bilgisayar matematiğinin en etkin biçimde kullanıldığı bir araştırma dalıdır

12-19-2012	#1
Prof. Dr. Sinsi	Graflar Kuramı Nedir? XVIII yy?da Euler?in çalışmaları sonucunda ortaya çıkan graflar kuramı, XX yy?ın başında König ve Kuratowski?nin, Cayley?in ve daha yakınlarda Berge, Erdös ve Harray?nin çalışmalarıyla bir matematik dalı haline geldi Bilgisayar alanında ve özellikle algoritmalar üzerinde yapılan araştırmalar, graflar kuramına yeni bir soluk getirdi Graflar kuramı, çok çeşitli uygulamalar için oluşturulan problemleri, noktalar ve noktalar arası bağlantılar yardımıyla çizilen konfigürasyonlara indirgeyerek çözme olanağı verir GRAFLAR KURAMI Graflar kuramının, << Königsberg (bugün Rusya?da Kaliningrad) Köprüleri>> denilen probleme kadar dayandığı kabul edilir 1736?da Euler?in çözdüğü bulmacaya benzer bir problem olan << Königsberg Köprüleri >> problemi, şöyle ifade edilebilir: kentin herhangi bir yerinden yola çıkıp, kentteki yedi köprüden yalnızca bir kez geçerek başlangıç noktasına geri dönmek mümkün müdür? Graflar kuramı, her şeyden önce çözümü aranan bir problemi ya da işi en etkin şekilde temsil edebilmeye ve düzenlemeye yarar Bu problem graf biçimine çevrildikten sonra, tüm amaçları yerine getirecek en hızlı veya en az masraflı yolu bulmak için sistematik yöntemler aranır Graflardan çok değişik uygulama alanlarında yararlanılır: ulaşım ağlarının optimizasyonunda (yol ya da bilgi ulaşımı), elektrik şebekeleri kavramında, haberleşme ağlarında, istatistiksel mekanikte, kimyasal formüllerde, bilgisayar kuramında, toplumsal bilimlerde, coğrafyada, mimarlıkta? GRAF NEDİR? Graf sözcüğünü ilk kez 1822?de İngiliz matematikçi JJ Sylvester kullandı, gaflar kuramı üzerine ilk kitabı ise 1936?da D König yayımladı Garf, bir noktalar(köşeler) kümesi ile bu noktaların arasındaki çizgiler ya da oklar(ayrıtlar) kümesi tarafından tanımlanan bir geometrik çizimdir Her ayrıtın ucunda gerektiğinde birbiri üzerine gelebilen iki köşe vardır Eğer grafın her ayrıtında bir başlangıç ve bir sonuç ucu ayırt ediliyorsa, bu graf yönlü olarak tanımlanır Grafların özellikleri farklı tipten problemleri niteler: - Eğer bir grafta, iki ayrı köşe tek bir ayrıtla birbirine bağlanıyorsa buna yalın graf denir - Eğer bir grafta iki ayrı köşe bir dizi kesintisiz ayrıtla birbirine bağlanıyorsa, buna bağlantılı graf denir Bir << ağaç >> kapalı yol içermeyen bağlantılı bir graftır Ağaçların ya da ağaç görünümlü grafların kullanılmasının örneklerine, veri tabanlarının yönetiminde rastlanır Bilgilerin nasıl düzenlendiğini izleyerek ağacı tanımak, onların incelenmesini kolaylaştırır ve optimize eder Bilgisayarlardaki buna koşut yapı amaçları ve hedefleri düzene koyan bir yöntem izlenerek gerçekleştirilir Bu alan, bilgisayar matematiğinin en etkin biçimde kullanıldığı bir araştırma dalıdır