Yönlendirilmiş Grafik ve Yönsüz Grafik
Grafik, köşeler ve kenarlardan oluşan matematiksel bir yapıdır. Grafik, bazı bağlantılar (kenarlarla temsil edilen) aracılığıyla bağlanan bir dizi nesneyi (köşelerle temsil edilir) temsil eder. Matematiksel gösterimler kullanılarak, bir grafik G ile temsil edilebilir; burada G=(V, E) ve V köşeler kümesidir ve E kenarlar kümesidir. Yönsüz bir grafikte, köşeleri birbirine bağlayan kenarlarla ilişkili bir yön yoktur. Yönlendirilmiş bir grafikte, köşeleri birbirine bağlayan kenarlarla ilişkili bir yön vardır.
Yönsüz Grafik
Daha önce bahsedildiği gibi, yönsüz bir grafik, grafikteki köşeleri birbirine bağlayan kenarlarda hiçbir yönün olmadığı bir grafiktir. Şekil 1, V={V1, V2, V3} köşe kümesiyle yönlendirilmemiş bir grafiği göstermektedir. Yukarıdaki grafikteki kenarlar kümesi V={(V1, V2), (V2, V3), (V1, V3)} şeklinde yazılabilir. Kenarların bir yönü olmadığı için V={(V2, V1), (V3, V2), (V3, V1)} şeklinde yazılmasına engel bir durum olmadığı da belirtilebilir. Bu nedenle, yönsüz bir grafikteki kenarlar sıralı çiftler değildir. Bu, yönsüz bir grafiğin ana özelliğidir. Yönlendirilmemiş grafikler, köşelerle temsil edilen nesneler arasındaki simetrik ilişkileri temsil etmek için kullanılabilir. Örneğin, bir dizi şehri birbirine bağlayan iki yönlü bir yol ağı, yönsüz bir grafik kullanılarak gösterilebilir. Şehirler grafikteki köşelerle temsil edilebilir ve kenarlar şehirleri birbirine bağlayan iki yönlü yolları temsil eder.
Yönlendirilmiş Grafik
Yönlendirilmiş bir grafik, köşeleri birbirine bağlayan grafikteki kenarların bir yöne sahip olduğu bir grafiktir. Şekil 2, V={V1, V2, V3} köşe kümesiyle yönlendirilmiş bir grafiği göstermektedir. Yukarıdaki grafikteki kenarlar kümesi V={(V1, V2), (V2, V3), (V1, V3)} şeklinde yazılabilir. Yönlendirilmemiş bir grafikteki kenarlar sıralı çiftlerdir. Biçimsel olarak, yönlendirilmiş bir grafikteki e kenarı, e=(x, y) sıralı çifti ile temsil edilebilir; burada x, e kenarının orijini, kaynağı veya başlangıç noktası olarak adlandırılan tepe noktasıdır ve tepe noktası y, son olarak adlandırılır., bitiş noktası veya bitiş noktası. Örneğin, tek yönlü yollar kullanarak bir dizi şehri birbirine bağlayan bir yol ağı, yönlendirilmemiş bir grafik kullanılarak gösterilebilir. Şehirler, grafikte köşeler ile temsil edilebilir ve yönlendirilmiş kenarlar, trafiğin yoldaki aktığı yönü dikkate alarak şehirleri birbirine bağlayan yolları temsil eder.
Yönlendirilmiş Grafik ile Yönlendirilmemiş Grafik arasındaki fark nedir?
Yönlendirilmiş bir grafikte kenar, sıralı bir çifttir; burada sıralı çift, iki köşeyi birbirine bağlayan kenarın yönünü temsil eder. Öte yandan, yönsüz bir grafikte, kenarla ilişkili bir yön olmadığından kenar sırasız bir çifttir. Yönlendirilmemiş grafikler, nesneler arasındaki simetrik ilişkileri temsil etmek için kullanılabilir. Yönlendirilmemiş bir grafikte her bir düğümün derece ve derece dışı eşittir, ancak bu yönlendirilmiş bir grafik için doğru değildir. Yönlendirilmemiş bir grafiği temsil etmek için bir matris kullanıldığında, matris her zaman simetrik bir grafik haline gelir, ancak bu yönlendirilmiş grafikler için doğru değildir. Yönlendirilmemiş bir grafik, her bir kenarı zıt yönde giden iki yönlendirilmiş kenarla değiştirerek yönlendirilmiş bir grafa dönüştürülebilir. Ancak, yönlendirilmiş bir grafiği yönsüz bir grafiğe dönüştürmek mümkün değildir.
