Boxicity
 | Bu madde, öksüz maddedir; zira herhangi bir maddeden bu maddeye verilmiş bir bağlantı yoktur. (Eylül 2022) |
Boxicity, çizge kuramı'ında kullanılan bir çizge sabitidir.1969 yılında Fred S. Roberts tarafından geliştirilmiştir. Örneğin bakınız Chandran, Francis & Sivadasan (2006) ve Chandran & Sivadasan (2007). Bir çizgenin boxicity sabiti, minimum boyutudur. Bunun için belirtilen çizge, yerleştirilmiş paralel kutuların ekseninin kesişim çizgesi olarak sunulabilir.Yani, çizgenin ve bir grup kutunun (kare, dikdörtgen vs.) köşeleri arasında bire bir ilişki olmak zorundadır öyle ki, eğer sadece ilişkili köşeleri birleştiren bir kenar varsa, iki kutu kesişir.
Örnekler
[değiştir | kaynağı değiştir]Yandaki çizgede, altı köşesi bulunan bir köşegen ve bir grup dikdörtgenin (iki boyutlu kutular) kesişiminin görülmektedir. Bu çizgede daha düşük boyutlarda bir kesişim gösterilemez. Bu çizgede, boxicity değeri 2'dir. Chandran, Francis & Sivadasan (2006) bu konuda bir algoritma yayımlamışlardır.
Kaynakça
[değiştir | kaynağı değiştir]- Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen (2006), Geometric representation of graphs in low dimension, arXiv:cs.DM/0605013.
- Chandran, L. Sunil; Sivadasan, Naveen (2007), "Boxicity and treewidth", Journal of Combinatorial Theory, Series B, 97 (5), ss. 733-744, doi:10.1016/j.jctb.2006.12.004, arXiv:/ 0505544 math.CO / 0505544.