Grafiği devrik - Transpose graph
Matematiksel ve algoritmik çalışmada grafik teorisi , zıddı , devrik veya ters a yöneliktir grafik G karşılık gelen kenarlarına uyumu ile kıyaslandığında ters çevrilmiş kenarlarının tüm köşe aynı kümesi bir yönlendirilmiş grafiktir G . Yani, eğer G, bir kenar içerir , sonra tersi / devrik / arasında ters G bir kenar içerir tersi ve yardımcısı.
gösterim
Adı tersi okların ters almak için karşılık gelen nedeni şöyledir: tersini mantığı bir içerme. Adı devrik çünkü komşuluk matrisi devrik yönlendirilmiş grafik olan devrik orijinal yönlendirilmiş grafiğin bitişiklik matrisi.
Tercih edilen terminoloji konusunda genel bir anlaşma yoktur.
Bunun tersi, hangi terminolojinin kullanıldığına ve gösterimin kaynağının hangi kitap veya makale olduğuna bağlı olarak G' , G T , G R veya diğer gösterimler olarak sembolik olarak gösterilir .
Uygulamalar
Bir grafik ile devrik arasında matematiksel olarak çok az fark olmasına rağmen, bilgisayar bilimlerinde verilen bir grafiğin nasıl temsil edildiğine bağlı olarak fark daha büyük olabilir . Örneğin, web grafiği için , bir köşenin giden bağlantılarını belirlemek kolaydır, ancak gelen bağlantıları belirlemek zordur, bu grafiğin tersine çevrilmesinde ise bunun tersi doğrudur. Bu nedenle, grafik algoritmalarında , grafiği üzerinde gerçekleştirilen işlemler için daha uygun bir forma sokmak için grafiğin tersine çevrilmesinin açık bir temsilini oluşturmak bazen yararlı olabilir. Bunun bir örneği, Kosaraju'nun güçlü bağlantılı bileşenler için algoritmasıdır ; bu algoritma , derinlik aramasını iki kez, bir kez verilen grafiğe ve ikinci kez de tersine çevirmeye uygular .
Ilgili kavramlar
Bir ters simetrik grafik olan bir grafiktir izomorfik izomorfik özel bir tür ile, kendi devrik grafik bu noktaların her kadar çiftleri.
Bunun tersi bir ilişki a ikili ilişki ilgili nesnelerin her biri bir sipariş ters ilişkisidir. İlişki yönlendirilmiş bir grafik olarak yorumlanırsa, bu grafiğin devrik ile aynı şeydir. Özellikle, kısmi bir düzenin ikili düzeni , bu şekilde, geçişli-kapalı bir yönlendirilmiş asiklik grafiğin yer değiştirmesi olarak yorumlanabilir .