Denkşekillilik (Isomorphism)


Yazan : Şadi Evren ŞEKER
İki şeklin birbirinden farklı ancak denk olması durumudur.

Bilgisayar bilimleri de dahil olmak üzere pek çok bilim ve mühendislik alanında kullanılan graf teorisine (graph theory) göre iki şekil birbirinden farklı çizilmiş ancak işlev ve değer olarak aynı olabilir.

Tanım ve örnek

Örneğin aşağıdaki iki şekli ele alalım:

bipartite1

Yukarıda verilen graftaki düğümler (nodes) ik ifarklı küme oluşturmak için aşağıdaki şekilde yerlerinden hareket ettirilmiş olsun:

bipartite2

Yukarıdaki bu yeni şekil ve ilk şekil arasında denklik söz konusudur. Buradaki denklik komşuluk anlamında düşünülebilir. Yani iki şekilde de bütün düğümlerin komşuları aynıdır. Ancak fark edileceği üzere iki şekildeki elamanların yerleri değiştirilmiştir.

Bu durumda yukarıdaki iki şekil için denkşekilli (isomorphic, izomorfik) denilebilir.

Yukarıdaki tanım için aynı zamanda kenar korumalı (edge preserving) birebir ve örten dönüşüm (bijection) terimi kullanılabilir.

Denkeşliliğin özellikleri

Şayet iki graf denkeşli ise bu grafların birisndeki döngü (cycle) sayısı diğerine eşittir.

Şayet iki graf denkeşli ise bu graflardan birisindeki toplam düğüm dereceleri (node order) diğerine eşittir.

Denkeşlilik Problemi (Isomorphism problem)

Denkeşlilik ile ilgili önemli bir problem iki grafın birbirine denk olduğunun tespitinde yaşanır. Elimizde iki farklı graf olduğunu ve bunların denkeşli (isomoprhic) olup olmadığını öğrenmek istediğimizi düşünelim.

Herşeyden önce bu problemi ilginç yapan, problemin polinom zamanda çözülüp çözülemeyeceğidir. Bu problem bu anlamda ilginçtir çünkü problemi ne NP ne de P kümesine ait değildir denilebilir.

Aslında bu tartışma daha derinlerde NP ⊃ P iddiasının doğruluğuna dayanmaktadır. Yani şayet NP, P nin üst kümesiyse (superset) bu durumda ikisi arasında başka bir küme olamaz. Ancak bazı araştırmacılar (örneğin Uwe Schöning) bu iki küme arasında alt ve üst hiyerarşik seviyeler bulunduğunu iddia etmişler ve denkşekillik gibi bazı problemleri bu kümeye dahil etmişlerdir.

İddiaya göre P altta ve NP üstte iki seviye olarak düşünülürse düşük hiyerarşik seviyedeki problemler P’ye ve yüksek hiyerarşik seviyedeki problemler NP’ye daha yakın kabul edilecektir.

Bütün bu iddiaların sebebi denkşekillik gibi problemlerin karmaşıklığının (complexity) hala ispatlanamamış olmasıdır.

Bu problemin farklı bir halinin karmaşıklığı bulunabilmektedir. Örneğin problemimizi biraz değiştirerek alt grafların (subgraphs) denkşekilliğini sorgulayacak olursak bu durumda problemimiz NP-Complete olarak sınıflandırılabilir.


« Öyler Yolu (Eulerian Path)   |   Düğüm Derecesi (Order of Node) »



Yorumlar

Kullanıcı girişi yaparak ya da zorunlu olan * alanlarını doldurarak yorum yapabilirsiniz.

İsminiz *

Email adresiniz *

Web siteniz

Mesajınızı buraya yazabilirsiniz:

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Denkşekillilik (Isomorphism)' isimli yazı 18 Jun 2009 tarihinde, saat: 01:55 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 354 defa okunmuştur.

Benzer yazıları algoritma analizi (teory of algorithms), graf teorisi (graph theory, çizge kuramı), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar
Yapılan Son Yorumlar
Yakın Yazılar
Bağlantılar