Benzersiz lavabo yönü - Unique sink orientation

İçinde matematik, bir benzersiz lavabo yönü bir satırın kenarlarının yönlendirmesidir politop öyle ki, politopun her yüzünde (yüzlerden biri olarak tüm politop dahil), tam olarak bir tepe tüm bitişik kenarların içe doğru yönlendirildiği (yani bu tepe noktasına doğru). Doğrusal bir amaç işlevi ile birlikte bir politop verilirse ve kenarlar, daha küçük amaç işlevi değerlerine sahip köşelerden daha büyük nesnel değerlere sahip köşelere yönlendirilirse, sonuç benzersiz bir havuz yönelimidir. Böylece, benzersiz lavabo yönleri modelleme için kullanılabilir doğrusal programlar gibi belirli doğrusal olmayan programların yanı sıra en küçük daire problemi.

Hiperküplerde

Bir hiperküpün benzersiz bir lavabo yöneliminde lavaboyu bulma sorunu, bir soyutlama olarak formüle edildi. doğrusal tamamlayıcılık problemleri tarafından Stickney ve Watson (1978) ve 2001 yılında "benzersiz lavabo yönelimi" olarak adlandırıldı (Szabó ve Welzl 2001 ). algoritma benzersiz havuzunu belirlemek için dzaman içinde boyutlu hiperküp cd için c < 2, büyük ölçüde daha küçük 2d tüm köşeleri incelemek için gereken süre. Oryantasyon, oryantasyonun oluşturduğu ek özelliğe sahip olduğunda Yönlendirilmiş döngüsüz grafiği, modelleme yapmak için benzersiz lavabo yönleri kullanıldığında LP tipi sorunlar, havuzun karekökünde üstel olarak beklenen zamanda rastgele bir algoritma kullanarak bulmak mümkündür. d (Gärtner 2002 ).

Basit politoplarda

Bir basit dboyutlu politop her köşenin tam olarak sahip olduğu bir politoptur d olay kenarları. Basit bir politopun benzersiz bir havuz yönünde, her alt kümesi k bir tepe noktasında gelen kenarlar v belirler kboyutsal yüz v eşsiz lavabodur. Bu nedenle, politopun tüm boyutlarının yüzlerinin sayısı (politopun kendisi dahil, ancak boş küme dahil değil), gelen kenarların alt kümelerinin sayısının toplamı ile hesaplanabilir,

nerede G(P) politopun grafiğidir ve diçinde(v) derece bir tepe noktasının (gelen kenar sayısı) v verilen yönde (Kalai 1988 ).

Daha genel olarak, basit bir politopun herhangi bir yönü için, aynı toplam, politopun bir yüzünün ve yüzün bir çukurunun gelen çiftlerinin sayısını sayar. Ve bir döngüsel olmayan yönelim her yüzün en az bir lavabosu olmalıdır. Bu nedenle, döngüsel olmayan bir yönelim, yalnızca ve ancak daha küçük bir toplamı olan başka bir döngüsel olmayan yönelim yoksa benzersiz bir havuz yönelimidir. Ek olarak, bir k- Verilen grafiğin düzenli alt grafiği, ancak ve ancak köşeleri bir biçim oluşturuyorsa, politopun bir yüzünü oluşturur. alt set en az bir döngüsel olmayan benzersiz lavabo yönlendirmesi için. Bu şekilde yüz kafes Politopun% 'si grafikten benzersiz bir şekilde belirlenir (Kalai 1988 ). Bu yapıya dayanarak, basit politopların yüz kafesleri, içindeki grafiklerinden yeniden oluşturulabilir. polinom zamanı kullanma doğrusal programlama (Friedman 2009 ).

Referanslar

  • Friedman, Eric J. (2009), "Polinom zamanında grafiğinden basit bir politop bulmak", Ayrık ve Hesaplamalı Geometri, 41 (2): 249–256, doi:10.1007 / s00454-008-9121-7, BAY  2471873.
  • Kalai, Gil (1988), "Grafiğinden basit bir politopu ayırt etmenin basit bir yolu", Kombinatoryal Teori Dergisi, Seri A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7, BAY  0964396.
  • Matoušek, Jiří (2006), "Hiperküpün benzersiz havuz yönlerinin sayısı", Kombinatorik, 26 (1): 91–99, CiteSeerX  10.1.1.5.491, doi:10.1007 / s00493-006-0007-0, BAY  2201286, S2CID  29950186.
  • Schurr, Ingo; Szabó, Tibor (2004), "Lavaboyu bulmak biraz zaman alıyor: lavaboya yönelik benzersiz küplerin lavabosunu bulmak için neredeyse karesel bir alt sınır", Ayrık ve Hesaplamalı Geometri, 31 (4): 627–642, doi:10.1007 / s00454-003-0813-8, BAY  2053502.
  • Stickney, Alan; Watson, Layne (1978), "Doğrusal tamamlayıcılık problemi için Bard-tipi algoritmaların Digraph modelleri", Yöneylem Araştırması Matematiği, 3 (4): 322–333, doi:10.1287 / bağlama.3.4.322, BAY  0509668.
  • Szabó, Tibor; Welzl, Emo (2001), "Küplerin benzersiz lavabo yönelimleri", 42. IEEE Bilgisayar Biliminin Temelleri Sempozyumu (Las Vegas, NV, 2001), Los Alamitos, CA: IEEE Computer Society, s. 547–555, CiteSeerX  10.1.1.25.2115, doi:10.1109 / SFCS.2001.959931, ISBN  978-0-7695-1116-0, BAY  1948744, S2CID  6597643.
  • Gärtner, Bernd (2002), "Kombinatoryal küpler üzerinde Random-Facet simpleks algoritması", Rastgele Yapılar ve Algoritmalar, 20 (3): 353–381, doi:10.1002 / rsa.10034.