Karmaşıktan Sadeliğe Doğru: İzomorfik Graf Teorisi

Karmakarışık olan bir yapının daha basit ve sade hale gelmesine olanak sağlar bazen de matematik…

18. yüzyılda Euler’in bir problemi üzerine ortaya çıkan ve günümüzde Königsberg Problemi olarak adlandırılan bir başlangıç yapan grafik kuramı 19. yüzyılda gerçekten gelişti; o zamandan beri de her alana uygulandı. Bugün insanlar (noktalar) arasındaki milyarlarca bağlantının (kenarların) her saniye değişen bir grafik oluşturduğu “world wide web”de çalışıyoruz.

Graf teorisi, çizge teorisi veya çizit teorisi grafikleri inceleyen matematik dalıdır. İzomorfik ise genelde matematikçilerin kullandığı, “eş” ve “aynı”anlamına gelen bir ifadedir.

Günümüzde ağlarla birbirimize bağlanmış durumdayız. Telefon ağları, metro ağları, internet ağları bunlara sadece bir kaç örnek. İşte bu ağlar aslında matematikçiler için çizgelerdir.

Herhangi bir metro grafik haritasına baktığımızda hangi istasyonların hangileriyle bağlantılı
olduğunu söyleyebiliriz. Bu bir haritadır; fakat istasyonların konumlandırılmasının aslında coğrafi açıdan nerede oldukları ile ilgisi yoktur, onları birleştiren hatların uzunluğunun da mesafelerle bir ilgisi yoktur. Bu harita bize demiryolu ağı içinde nasıl hareket edebileceğimizi gösterir; ne kadar
uzağa gideceğimizi ya da yolculuğumuzun ne kadar süreceğini söylemez. Bize sadece bilmemiz gerekeni söyler.

Demiryolu haritası topolojik grafiğe bir örnektir. Topolojide bir grafik (yani ağ) köşe noktalarının , burada istasyonların, birbirine “kenarlar”la (burada demiryolu hatlarıyla) birleştirildiği bir şemadır.

Şimdi bunu daha iyi anlamak için farklı görünen ancak aslında aynı olan iki grafiğe bir göz atalım:

Bu iki haritada bağlantıların, istasyonların ve düğüm yerlerinin aynı olduğunu görebilirsiniz. Ancak sağdakinde istasyonların konumları, coğrafi harita ile karşılaştırıldığında, okunmasını kolaylaştırmak için değiştirilmiş durumda. Yani aslında bu iki ağ, her ne kadar farklı gibi algılansa da izomorf yani aynı.

Peki, iki grafiğin izomorfik olup olmadığı nasıl anlaşılır?

Bunun için iki grafiğin de, kenar sayısı, düğüm sayısı ve düğüm dereceleri aynı olmalıdır.

Graf izomorfizm teoremi aslında sadece bize farklı gösterimlerle verilen iki grafiğin izomorf olmasının mümkün olup olmadığını sormuyor bir adım daha öteye giderek bunların oluşmasını sağlayan algoritmaları da veriyor.

Önce merkezler seçilir ve arasındaki ağlar belirlenir. Yanyana olan duraklar ya da yerler düğümlerle bağlanır. Daha sonra köşe noktalarına verilen numaralar düğümlerle birlikte birleştirilir. Elbette bu iş karmaşık haritalarda daha zor bir durum alacaktır. Bu karmaşıklığın sebebi bağlantı noktalarının fazla olmasıdır.

İşte matematikçiler bu şekilde karmakarışık olan bir merkezin haritasını daha kolay şekilde insanların anlamasına yardımcı olmak için en merkezden başlayarak gittikçe dışa doğru yönelerek bir harita çıkarmaya çalışırlar ve yukarıda bahsettiğimiz teoremi kullanılırlar. Ama dikkat etmemiz gereken bir nokta şu…

Eğer herhangi bir merkez diğer bir merkez ile yanlış bağlanırsa o zaman haritanın tüm hatları yanlış olacaktır. Bu teori aslında hayatımızda karmakarışık olan bir yapının daha basit ve sade hale gelmesine olanak sağlıyor, incelemelerin daha basit bir şekilde oluşturulmasına olanak kılıyor. Hayatının her yerinde bu teoriyi aslında siz de kullanıyorsunuz!

Referans

(1) – https://plus.maths.org/content/maths-minute-graph-isomorphism

Matematiksel

Yazıyı Hazırlayan: Sibel Çağlar

Kadıköy Anadolu Lisesi, Marmara Üniversitesi, ardından uzun süre özel sektörde matematik öğretmenliği, eğitim koordinatörlüğü diye uzar gider özgeçmişim… Önemli olan katedilen değil, biriktirdiklerimiz ve aktarabildiklerimizdir bizden sonra gelenlere... Eğitim sisteminin içinde bulunduğu çıkmazı yıllarca iliklerimde hissettikten sonra, peki ama ne yapabilirim düşüncesiyle bu web sitesini kurmaya karar verdim. Amacım bilime ilgiyi arttırmak, bilimin özellikle matematiğin zihin açıcı yönünü açığa koymaktı. Yolumuz daha uzun ve zorlu ancak en azından deniyoruz.

Bunlara da Göz Atın

Beatles’ın Gizemini Matematikle Çözmek

Beatles’ın tek bir notasının sırrının açıklanması 45 yıldan fazla sürmüştür. Müziğin yarattığı tınıyı matematik çözmüştür. …

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.

ga('send', 'pageview');