Ağlar her yerde. Onlara her gün, internet şeklinde ya da bağımlı olduğumuz toplumsal, ulaşım ve hizmet ağları ile karşılaşırız. Matematiksel olarak, bir ağ, bir grafik örneğidir: Bağlantılarla (kenarlar da denir) birleştirilmiş düğümler kümesi (köşeler olarak da adlandırılır). Sorun, aynı grafiğin farklı görünüşlerde görünebilmesidir – ki bu da görünüşte farklı iki grafinin aslında aynı olup olmadığını anlamanın ne kadar zor olduğunu irdeler. Bu soru, grafik izomorfizm problemi olarak bilinir.
Londra Metrosunun coğrafi olarak doğru bir haritasının bir parçası (üstteki, Wikimedia) ve gerçek haritadaki ağın (kabaca) karşılık gelen kısmı (alttaki) veiliyor.
Farklı görünen ancak aslında aynı olan iki grafiğe bir örnek, London Underground haritasından gelmektedir. Okumayı kolaylaştırmak için istasyonların göreceli konumları, coğrafi harita ile karşılaştırıldığında değiştirildi. Tüp metnindeki Yeraltı ağı, doğru bir şekilde çizildiğinde benzediğinden farklı görünüyor, ancak ikisi izomorf: her bir köşeyi ve her kenarı, grafiğin bağlantısını koruyacak şekilde (köşeye bağlantıları) bir grafiği tam olarak diğerinde bir köşe veya kenara eşleyebilirsiniz (ve tam tersi). Bu örnekte, iki ağın izomorf olduğunu başından beri biliyoruz; hepsi aynı fiziksel tren ağını temsil ediyor ancak bilgi olmaksızın, gerçekte aynı olduklarını anlamak biraz süre alabilir.
Yorum yazabilmek için oturum açmalısınız.