Yönlendirilmiş ve Yönlendirilmemiş Grafik Arasındaki Fark

Yönlendirilmiş ve Yönlendirilmemiş Grafik

Grafik, köşe ve kenar kümesinden oluşan matematiksel bir yapıdır. Bir grafik, bazı bağlantılarla (kenarlarla temsil edilen) bağlanan bir dizi nesneyi (köşelerle temsil edilir) temsil eder. Matematiksel gösterimler kullanarak, bir grafik G ile temsil edilebilir; burada G = (V, E) ve V, köşe kümesidir ve E, kenar kümesidir. Yönlendirilmemiş bir grafikte, köşeleri birleştiren kenarlarla ilişkili bir yön yoktur. Yönlendirilmiş bir grafikte, köşeleri birleştiren kenarlarla ilişkili bir yön vardır.

Yönlendirilmemiş Grafik

Daha önce belirtildiği gibi, yönlendirilmemiş bir grafik, kenarlarda grafikteki köşeleri bağlayan bir yön bulunmayan bir grafiktir. Şekil 1, V = V1, V2, V3 köşe kümesine sahip yönlendirilmemiş bir grafiği göstermektedir. Yukarıdaki grafikteki kenar kümesi V = (V1, V2), (V2, V3), (V1, V3) olarak yazılabilir. Kenarların bir yönü olmadığı için kenar kümesinin V = (V2, V1), (V3, V2), (V3, V1) olarak yazılmasını engelleyen hiçbir şey olmadığı da not edilebilir. Bu nedenle, yönlendirilmemiş bir grafikteki kenarlar sıralı çiftler değildir. Bu, yönlendirilmemiş 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önlendirilmemiş bir grafik kullanılarak temsil edilebilir. Şehirler, grafikteki köşe noktaları ile temsil edilebilir ve kenarlar, şehirleri birbirine bağlayan iki yönlü yolu temsil eder.

Yönlendirilmiş grafik

Yönlendirilmiş grafik, grafikte köşeleri birbirine bağlayan 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 kenar kümesi V = (V1, V2), (V2, V3), (V1, V3) olarak yazılabilir. Yönlendirilmemiş bir grafikteki kenarlar sıralı çiftlerdir. Resmi olarak, yönlendirilmiş bir grafikteki kenar e, e = (x, y) sıralı çifti ile temsil edilebilir; burada x, e kenarının başlangıç ​​noktası, kaynağı veya başlangıç ​​noktası olarak adlandırılan tepe noktasıdır ve y noktasına son noktası adı verilir , sonlandırma tepe noktası veya terminal noktası. Örneğin, bir şehirleri tek yönlü yollar kullanarak birbirine bağlayan bir yol ağı, yönlendirilmemiş bir grafik kullanılarak temsil edilebilir. Şehirler, grafikteki köşe noktaları ile temsil edilebilir ve yönlendirilen kenarlar, trafiğin yolda 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ı çiftin iki köşeyi birbirine bağlayan kenarın yönünü temsil ettiği sıralı bir çifttir. Öte yandan, yönlendirilmemiş bir grafikte kenar, sıralanmamış bir çifttir, çünkü bir kenarla ilişkili yön yoktur. Yönlendirilmemiş grafikler, nesneler arasındaki simetrik ilişkileri temsil etmek için kullanılabilir. Yönlendirilmemiş bir grafikteki her düğümün derecesi ve derecesi 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ırken, matris her zaman simetrik bir grafik haline gelir, ancak bu yönlendirilmiş grafikler için geçerli değildir. Yönlendirilmemiş bir grafik, her bir kenarı zıt yöne giden iki yönlendirilmiş kenar ile değiştirerek yönlendirilmiş bir grafiğe dönüştürülebilir. Ancak, yönlendirilmiş bir grafiği yönlendirilmemiş bir grafiğe dönüştürmek mümkün değildir.