Elektrik Devrelerinin Çözümünde Kullanılan Graph Teorisi Nasıl Bulundu?

Devre çözümlemesinde devreyi oluşturan öğelerin aralarındaki bağlantıların matematiksel olarak ifade edilmesini kolaylaştıran Graph Teorisi’ni kim ve nasıl buldu? Aslında basit bir matematiksel bilmeceye dayanıyor. “Königsberg’in Yedi Köprüsü” adındaki Königsberg köprülerinden esinlenerek ortaya atılan ünlü bir matematik problemi sayesinde. Problemin detayı yazının devamında.

A- A+

07.07.2013 tarihli yazı 43370 kez okunmuştur.

Königsberg, 16.Yüzyıl’da Prusya’da Pregel Nehri’nin üzerine yerleşmiş o zamanki düklerin yaşadığı bir şehirdi. (Şu an ki batı Rusya’da Kaliningrad bölgesi). Pregel Nehri, şehrin içine doğru akardı ve içinde küçük bir ada oluşturmuştu. Nehre aşağıdaki şekilde olduğu gibi yedi köprü inşa edildi ve o bölge dört kısma ayrıldı.

Königsberg’in Yedi Köprüsü Problemi ise şu;

Bütün köprülerden bir ve yalnız bir kez geçmek koşulu ile tam bir turla yürüyüş yapılabilir mi?

Bu soru ilk olarak 1736’da matematiğin dallarından biri olan Graph Teorisi’ni bulmuş İsviçreli matematikçi Leonhard Euler tarafından cevaplandırılmıştır.

Euler’in Çözümü

Yukarıdaki şekilde kara parçaları harflerle, köprüler ise sayılarla işaretlenmiştir. Önce çözümü biraz daha kolaylaştırmak ve şekli gereksiz bileşenlerden arındırmak amacıyla kara parçalarının noktalar, köprülerin ise bu noktaları birleştiren çizgiler olarak gösterildiği ikinci bir şekil yani çizge (graph) çizilir. Çizgiler graph elemanı, noktalar düğüm, düğüme bağlı olan elemanların sayısı ise düğüm derecesi olarak adlandırılmak üzere soru, çizgenin herhangi bir düğümünden başlayarak yedi elemanının her birini bir ve yalnız bir kez kullanarak dolaşma problemine dönüşmüş olur.

Örneğin A düğümünün derecesi 3 tanedir çünkü ona bağlı eleman veya soruya göre köprü 3 tane olduğundan düğüm derecesi 3’tür. Aynı şekilde B ve D’nin de düğüm dereceleri 3’tür. C’nin düğüm derecesi ise 5’tir.

Euler şunu iddaa etmekte; Bir düğüm başlangıç veya bitiş düğümü değilse, o bir düğüme gelindiğinde(A,B,C veya D) turun tamamlanması için o düğümden ayrılmak gerekecektir. Dolayısıyla ayrılması gereken düğümler çift dereceleri olmalıdır. Örneğin B düğümüne gelindiğinde oradan ayrılmak istense turu tam ve bir kez tamamlaması için B düğümünün çift dereceli olması lazım ama B düğümünün derecesi 3 yani tek olduğundan hepsi bir kez tam bir tur dolaşılamaz. Aynı şekilde A,C ve D düğümü içinde bu durum geçerlidir. Dolayısıyla bu düğüm ya gezintinin bitiş düğümü olmalıdır ya da başlangıç düğümü olarak seçilmelidir ki ikinci gelişte çıkış yolu bulunabilsin. Buna göre tek dereceli düğüm sayısı ikiden fazlaysa gezinti tamamlanamayacaktır.

►İlginizi Çekebilir: Leonhard Euler Kimdir?

Yürüyüşün sonunda başlangıç noktasına dönülebilmesi içinse bütün düğümler çift dereceli olmalıdır. Böylece, başlangıç ve bitiş düğümü aynı olan ve her bir elemanı sadece ve en az bir kez içeren tur tamamlanabilsin. Yani sorunun cevabı, bütün köprülerden bir ve yalnız bir kez geçmek koşulu ile tam bir turla yürüyüş yapılamaz, imkansızdır.

Leonhard Euler’in bu araştırmaları matematikte tamamıyla yeni bir dal olan çizge kuramının(Graph Teorisi) ilk teoremi ve topolojinin keşfinin habercisi olmuştur.

Günümüzde Graph Teorisi

Graph Teorisi, bir sürü uygulama alanı olan yeni matematiğin oluşumunda çok üretken bir yapıya sahip matematiğin son derece gelişmiş, önemli bir alanıdır. Yakın zamana kadar pek uygulama olanağı bulunmayan ancak bilgisayara dayanan yeni yöntemlerin gelişmesi ile elektrik mühendisliğinde de çok geniş bir alanı kapsayan bir matematik kolu oldu. Birçok problem Graph Teorisi’yle kolay anlaşılır ve çözülebilir (belki çok kolay çözülemeyen soruları bile). Devre çözümleri, ulaşım, planlama, zaman programlaması, elektrik şebekeleri gibi bir çok kullanım alanı vardır.

Kaynak :

► www.jcu.edu