İzomorfizm grafiği, tek bir grafiğin birden fazla forma sahip olabildiği bir grafik olarak tanımlanabilir. Bu, iki farklı grafiğin aynı sayıda kenara, köşeye ve aynı kenar bağlantısına sahip olabileceği anlamına gelir. Bu tür grafikler izomorfizm grafikleri olarak bilinir. Bir izomorfizm grafiği örneği şu şekilde açıklanmaktadır:
Yukarıdaki grafik aşağıdakileri içermektedir:
- Aynı grafik birden fazla biçimde temsil edilir.
- Dolayısıyla bu grafiklerin izomorfizm grafikleri olduğunu söyleyebiliriz.
Grafik izomorfizminin koşulları
Herhangi iki grafik, aşağıdaki dört koşulu karşılıyorsa izomorfizm olarak bilinecektir:
dizi olarak listele
- Verilen grafiklerde eşit sayıda köşe olacaktır.
- Verilen grafiklerde eşit sayıda kenar olacaktır.
- Verilen grafiklerde eşit miktarda derece dizisi olacaktır.
- İlk grafik {v1, v2, v3, … köşelerinin yardımıyla k uzunluğunda bir döngü oluşturuyorsa. vk} ise, o zaman başka bir grafiğin de {v1, v2, v3, … köşe noktalarının yardımıyla aynı uzunluktaki k aynı döngüyü oluşturması gerekir. vk}.
Not: Bir grafiğin Derece dizisi, tüm köşelerin artan sırada derecelerinin dizisi olarak tanımlanabilir.
Önemli noktalar
- Herhangi iki grafiğin izomorfizm olması için gerekli koşullar yukarıda tanımlanan dört koşuldur.
- Verilen grafiklerin izomorfik olduğunu göstermek için yukarıda tanımlanan koşulların yeterli olması şart değildir.
- Eğer iki grafik yukarıda tanımlanan dört koşulu sağlıyorsa, o zaman bile grafiklerin mutlaka izomorfizm göstermesi gerekli değildir.
- Eğer grafik herhangi bir koşulu sağlayamıyorsa grafiklerin kesinlikle bir izomorfizm olmadığını söyleyebiliriz.
Grafik izomorfizmi için yeterli koşullar
Herhangi iki grafiğin izomorfizm olduğunu kanıtlamak istiyorsak, iki grafiğin kesinlikle izomorfizm olduğunu garanti etmemizi sağlayacak bazı yeterli koşullar vardır. İki grafik, yukarıdaki dört koşulun tümünü başarılı bir şekilde temizlendiğinde, ancak o zaman bu grafiklerin aşağıda açıklanan yeterli koşullara sahip olup olmadığını kontrol edeceğiz:
- Her iki grafiğin tamamlayıcı grafikleri izomorfizm ise bu durumda bu grafikler mutlaka izomorfizm olacaktır.
- Her iki grafiğin bitişik matrisleri aynıysa, bu durumda bu grafikler bir izomorfizm olacaktır.
- Bir grafiğin bazı köşelerinin silinmesiyle iki grafiğin karşılık gelen grafikleri elde ediliyorsa ve diğer görüntülerdeki karşılık gelen görüntüleri izomorfizm ise, ancak o zaman bu grafikler izomorfizm olmayacaktır.
İki grafik yukarıdaki koşullardan herhangi birini sağladığında, bu grafiklerin kesinlikle izomorfizm olduğunu söyleyebiliriz.
Grafik İzomorfizm Örnekleri
Aşağıda açıklanan birçok grafik izomorfizm örneği vardır:
Örnek 1:
Bu örnekte aşağıdaki grafiklerin izomorfizm olup olmadığını gösterdik.
Çözüm: Bunun için aşağıda açıklanan grafik izomorfizminin dört koşulunun tamamını kontrol edeceğiz:
Durum 1:
- Grafik 1'de toplam 4 adet köşe vardır, yani G1 = 4.
- Grafik 2'de toplam 4 adet köşe vardır, yani G2 = 4.
Burada,
Hem G1 hem de G2 grafiğinde eşit sayıda köşe vardır. Yani bu grafikler koşul 1'i sağlıyor. Şimdi ikinci koşulu kontrol edeceğiz.
Durum 2:
- Grafik 1'de toplam 5 adet kenar vardır, yani G1 = 5.
- Grafik 2'de toplam 6 adet kenar vardır, yani G2 = 6.
Burada,
G1 ve G2 grafiklerinin her ikisinde de eşit sayıda kenar yoktur. Yani bu grafikler koşul 2'yi karşılamıyor. Şimdi geri kalan tüm koşulları kontrol edemiyoruz.
Çünkü bu grafikler koşul 2'yi ihlal etmektedir. Yani bu grafikler bir izomorfizm değildir.
∴ Grafik G1 ve grafik G2 izomorfizm grafikleri değildir.
Örnek 2:
Bu örnekte aşağıdaki grafiklerin izomorfizm olup olmadığını gösterdik.
Çözüm: Bunun için aşağıda açıklanan grafik izomorfizminin dört koşulunun tamamını kontrol edeceğiz:
Durum 1:
- Grafik 1'de toplam 4 adet köşe vardır, yani G1 = 4.
- Grafik 2'de toplam 4 adet köşe vardır, yani G2 = 4.
- Grafik 3'te toplam 4 adet köşe vardır, yani G3 = 4.
Burada,
G1, G2 ve G3 grafiklerinin tümünde eşit sayıda köşe vardır. Yani bu grafikler koşul 1'i sağlıyor. Şimdi ikinci koşulu kontrol edeceğiz.
Durum 2:
- Grafik 1'de toplam 5 adet kenar vardır, yani G1 = 5.
- Grafik 2'de toplam 5 adet kenar vardır, yani G2 = 5.
- Grafik 3'te toplam 4 adet kenar vardır, yani G2 = 4.
Burada,
- Hem G1 hem de G2 grafiğinde eşit sayıda kenar vardır. Yani bu grafikler koşul 2'yi karşılıyor.
- Ancak (G1, G2) ve G3 grafiklerinde eşit sayıda kenar yoktur. Dolayısıyla (G1, G2) ve G3 grafikleri koşul 2'yi karşılamamaktadır.
Çünkü (G1, G2) ve G3 grafikleri koşul 2'yi ihlal etmektedir. Dolayısıyla bu grafiklerin bir izomorfizm olmadığını söyleyebiliriz.
∴ G3 grafiği ne G1 grafiğiyle ne de G2 grafiğiyle izomorfizmdir.
G1 ve G2 grafikleri 2. koşulu sağladığına göre bu grafiklerin izomorfizm olabileceğini söyleyebiliriz.
∴ G1 ve G2 grafikleri izomorfizm olabilir.
Şimdi G1 ve G2 grafikleri için üçüncü koşulu kontrol edeceğiz.
Durum 3:
- Grafik 1'de s dizisinin derecesi {2, 2, 3, 3}'tür, yani G1 = {2, 2, 3, 3}.
- Grafik 2'de s dizisinin derecesi {2, 2, 3, 3}'tür, yani G2 = {2, 2, 3, 3}.
Burada
Hem G1 hem de G2 grafiğinde eşit sayıda derece dizisi vardır. Yani bu grafikler koşul 3'ü karşılıyor. Şimdi dördüncü koşulu kontrol edeceğiz.
Durum 4:
Grafik G1, {2, 3, 3} köşelerinin yardımıyla uzunluğu 3 olan bir döngü oluşturuyor.
Grafik G2 ayrıca {2, 3, 3} köşelerinin yardımıyla uzunluğu 3 olan bir döngü oluşturur.
Burada,
Her iki grafiğin de aynı döngüyü içerdiğini gösteriyor çünkü hem G1 hem de G2 grafikleri {2, 3, 3} köşelerinin yardımıyla 3 uzunluğunda bir döngü oluşturuyor. Yani bu grafikler koşul 4'ü karşılıyor.
Böylece,
- G1 ve G2 grafikleri yukarıdaki dört gerekli koşulun tamamını karşılamaktadır.
- Yani G1 ve G2 bir izomorfizm olabilir.
Şimdi G1 ve G2 grafiklerinin izomorfizm olduğunu göstermek için yeterli koşulları kontrol edeceğiz.
Yeterli Koşulların Kontrolü
Öğrendiğimiz gibi, eğer her iki grafiğin tamamlayıcı grafikleri izomorfizm ise, iki grafiğin de mutlaka bir izomorfizm olacağını öğrendik.
demetleri python sıralama
Böylece G1 ve G2'nin aşağıdaki şekilde açıklanan tamamlayıcı grafiklerini çizeceğiz:
Yukarıdaki G1 ve G2 tamamlayıcı grafiklerinde her iki grafiğin de izomorfizm olduğunu görebiliriz.
∴ G1 ve G2 grafikleri izomorfizmdir.
Örnek 3:
Bu örnekte aşağıdaki grafiklerin izomorfizm olup olmadığını gösterdik.
Çözüm: Bunun için aşağıda açıklanan grafik izomorfizminin dört koşulunun tamamını kontrol edeceğiz:
Durum 1:
- Grafik 1'de toplam 8 adet köşe vardır, yani G1 = 8.
- Grafik 2'de toplam 8 adet köşe vardır, yani G2 = 8.
Burada,
Hem G1 hem de G2 grafiğinde eşit sayıda köşe vardır. Yani bu grafikler koşul 1'i sağlıyor. Şimdi ikinci koşulu kontrol edeceğiz.
Durum 2:
- Grafik 1'de toplam kenar sayısı 10'dur yani G1 = 10'dur.
- Grafik 2'de toplam kenar sayısı 10'dur yani G2 = 10'dur.
Burada,
Hem G1 hem de G2 grafiğinde eşit sayıda kenar vardır. Yani bu grafikler koşul 2'yi sağlıyor. Şimdi üçüncü koşulu kontrol edeceğiz.
Durum 3:
- Grafik 1'de s dizisinin derecesi {2, 2, 2, 2, 3, 3, 3, 3}'tür, yani G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- Grafik 2'de s dizisinin derecesi {2, 2, 2, 2, 3, 3, 3, 3}'tür, yani G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Burada
Hem G1 hem de G2 grafiğinde eşit sayıda derece dizisi vardır. Yani bu grafikler koşul 3'ü karşılıyor. Şimdi dördüncü koşulu kontrol edeceğiz.
Durum 4:
- Grafik G1, 3. derece köşelerin yardımıyla uzunluğu 4 olan bir döngü oluşturuyor.
- G2 grafiği köşelerin yardımıyla 4 uzunluğunda bir döngü oluşturmuyor çünkü köşeler bitişik değil.
Burada,
Hem G1 hem de G2 grafikleri aynı uzunlukta aynı döngüyü oluşturmaz. Yani bu grafikler koşul 4'ü ihlal ediyor.
Çünkü G1 ve G2 grafikleri koşul 4'ü ihlal etmektedir. Yani koşul 4'ün ihlali nedeniyle bu grafikler izomorfizm olmayacaktır.
∴ G1 ve G2 grafikleri izomorfizm değildir.