bir bipartit grafikte geçiş noktalarının sayısının en aza indirilmesi

Aşağıdaki algoritma sorun bana oluştu gösterildiği gibi sütunlarda. Her bir sütunun içindeki düğümleri, kenar geçişlerinin sayısını en aza indirecek şekilde nasıl yeniden düzenleyebiliriz? Bu problemin genel grafikler için NP-zor olduğunu biliyorum (link), ancak grafiğin iki bölümlü olduğunu düşünürsek bazı hileler var mı? Bir takibi olarakbir bipartit grafikte geçiş noktalarının sayısının en aza indirilmesi

, sadece v için kenarları üçüncü bir sütun w ne varsa? Ya da dahası?

kaynak

2013-11-20 Imre Kerr

Yani grafik ile bir dosya hazırlamak sadece yükledikten sonra İsterseniz * iki sütun * (her bir alt grafik için bir tane) veya düğümler bir arbitraya yerleştirilebilir mi? ry yolu? –

En uygun çözümü veya yaklaşımı istiyor musunuz? (güzel soru btw) –

@arturgrzesiak Düğümler hala iki sütun halinde olmalıdır. Sorunu daha net hale getirmek için düzenleyeceğim. –

Gorey ve Johnson geçiş numarasına orijinal kağıt aynı zamanda kenar geçişleri sayısını en aza indirir bipartit grafikler için NP-zor olduğunu kanıtladı söz kağıt On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi. Aslında, tek bir sütun için en iyi sıra anlatılır bile bu iş de NP-zor : a bipartit grafiktir Verilen

, bir 2-katmanlı bir çizim ile ilgili birinci düğüm grubu V düğümleri yerleştirme oluşur bir düz çizgi L1 ve düğümleri ikinci düğümde W bir paralel çizgi L2'ye ayarlar. 'u minimize etme problemi, 2 katmanlı çizimde arklar arasındaki geçişlerin sayısı ilk olarak Harary ve Schwenk tarafından tanıtılan idi. Tek taraflı geçiş minimizasyonu probleminde, L1'e yerleştirilecek düğümlerin bir sıralamasını , yani ark geçişlerinin minimuma indirildiğini ( no'lu W2'deki düğümlerin verildiği ve sabitlendiği sırada) bulmayı ister. Problemin 'un uygulamaları VLSI düzenlerinde ve hiyerarşik çizimlerde bulunabilir. Bununla birlikte, iki taraflı ve tek taraflı problemlerin sırasıyla, Garey ve Johnson ve Eades ve Wormald tarafından NP-sert olduğu gösterilmiştir.

kaynak

2013-11-20 22:14:49

Bu kağıt tam olarak aradığım şey gibi görünüyor. Teşekkürler! –

Peter de Rivaz bunun NP-Hard olduğunu belirtti, ancak yine de bazı yaklaşımlarla sorun çıkarsanız, aşağıdaki çözümle devam edebilirsiniz.

İlk düşüncem grafik düzeni için bazı güç temelli algoritma kullanmaktı, ancak uygulamak biraz yorucu olabilir. Ama hey, tüm işinizi sizin için yapabileceğiniz bu harika program graphviz.org var.

graph G{ 
    {rank=same A B C D E} 
    {rank=same F G H K I J} 

    A -- F; 
    A -- G; 
    A -- K; 
    A -- I; 
    A -- H; 
    A -- J; 

    B -- G; 

    C -- G; 
    C -- J; 

    D -- K; 
    D -- I; 
}

Run: dot -Tpng yourgraph -o yourgraph.png

ve ücretsiz :-) için bu gibi şeyler olsun:

enter image description here

kaynak

2013-11-20 22:30:38

bir bipartit grafikte geçiş noktalarının sayısının en aza indirilmesi

cevap

İlgili konular