Denkşekillilik (Isomorphism) – Bilgisayar Kavramları
Home / algoritma analizi (teory of algorithms) • graf teorisi (graph theory, çizge kuramı) • veri yapıları / Denkşekillilik (Isomorphism)
İ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:
Yukarıda verilen graftaki düğümler (nodes) ik ifarklı küme oluşturmak için aşağıdaki şekilde yerlerinden hareket ettirilmiş olsun:
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.
Ş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.