Kare grafik - Squaregraph
Olarak grafik teorisi , bir dalı matematik bir squaregraph türüdür yönsüz grafik olabilir , düzlem üzerinde çizilen her sınırlı olduğu şekilde yüz a, dörtgen ve her köşe üç veya daha az komşuları ile sınırsız bir yüzüne doğrudan yer almaktadır.
İlgili grafik sınıfları
Squaregraphs özel durumlar olarak dahil ağaçlar , ızgara grafikler , dişli grafikler ve grafikleri polyominos .
Düzlemsel grafikler olmanın yanı sıra , karegraflar medyan grafiklerdir , yani her üç u , v ve w köşesi için, üç köşenin her bir çifti arasındaki en kısa yollarda uzanan benzersiz bir medyan köşe m ( u , v , w ) vardır. . Daha genel olarak orta grafikler gibi, squaregraphs da kısmi küp : bunların köşe ile etiketlenebilir ikili dizeleri şekilde Hamming uzaklığı dizgileri arasındaki köşe arasındaki en kısa yolu mesafesine eşittir.
Bir dörtlü olarak bir araya a, her iki bölge için her bir bölgenin (dörtgensel paralel kenarlarının bir denklik sınıfı) ve bir kenar, bir köşe yaparak squaregraph elde edilen grafik daire grafik bir tarafından belirlenen üçgen içermeyen biriminin akor diyagramı disk.
Karakterizasyon
Kare grafikler, düzlemsel yerleştirmelerinden farklı olarak birkaç şekilde karakterize edilebilir:
- Bunlar medyan grafikleri bir şekilde içermezler kaynaklı alt grafiği sonsuz ailesinin herhangi bir üyesini yasak grafikler . Bu yasak grafikler küp (vardır simpleks grafik arasında K 3 ), Kartezyen ürün bir kenar ve bir pençesi K 1,3 (pençe tek yönlü grafik) ve meydana gelen grafikler dişli grafik bir daha tepe ekleyerek tekerleğin göbeğine bağlı (yalıtılmış bir tepe noktasına sahip bir çevrimin ayrık birleşiminin tek yönlü grafiği).
- Bunlar bağlanır ve grafiklerdir bipartit , (isteğe bağlı bir tepe eğer böyle R bir şekilde alınır kök ), her köşe yakın en az iki komşu olan r , ve bu şekilde her bir tepe de v , bağlantı v (bir grafiktir v'ye her kenar olayı için bir tepe noktası ve v ) içeren her 4 döngü için bir kenar , ya üçten büyük bir uzunluk döngüsü ya da yolların ayrık birleşimidir.
- Bunlar ikili grafikleri ait hatların düzenlemeler de hiperbolik düzlem üç karşılıklı olarak kesişen çizgiler yok.
Algoritmalar
Kareköklerin bir kökten uzaklık ve köşelerin bağlantıları açısından karakterizasyonu, belirli bir grafiğin bir kare grafik olup olmadığını test etmek için doğrusal bir zaman algoritmasının bir parçası olarak , daha karmaşık doğrusal olanı kullanmaya gerek kalmadan , genişlikte ilk arama ile birlikte kullanılabilir. rastgele grafiklerin düzlemsellik testi için zaman algoritmaları .
Kare grafikler üzerindeki çeşitli algoritmik problemler, daha genel düzlemsel veya medyan grafiklerden daha verimli bir şekilde hesaplanabilir; örneğin, Chepoi, Dragan & Vaxès (2002) ve Chepoi, Fanciullini & Vaxès (2004), kare grafiklerin çapını hesaplamak ve diğer tüm köşelere maksimum mesafeyi en aza indiren bir tepe noktası bulmak için doğrusal zaman algoritmaları sunar .
Notlar
Referanslar
- Bandelt, Hans-Jürgen; Chepoi, Victor; Eppstein, David (2010), "Sonlu ve sonsuz kare grafiklerin kombinatorik ve geometrisi", SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137 / 090760301 , S2CID 10788524 .
- Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), "Düzlemsel kuadrangülasyonlarda ve üçgenlemelerde merkez ve çap problemi", Proc. 13th Annu. ACM – SIAM Symp. Ayrık Algoritmalar (SODA 2002) , s. 346–355 .
- Chepoi, Victor; Fanciullini, Clémentine; Vaxès, Yann (2004), "Bazı düzlem üçgenlemelerde ve kuadrangülasyonlarda medyan problemi", Hesaplamalı Geometri , 27 (3): 193–210, doi : 10.1016 / j.comgeo.2003.11.002 .
- Peterin, Iztok (2006), "Düzlemsel medyan grafiklerin karakterizasyonu" , Tartışmalar Mathematicae Graph Theory , 26 (1): 41–48, doi : 10.7151/dmgt.1299
- Soltan, P .; Zambitskii, D .; Prisǎcaru, C. (1973), Grafikler ve Çözümlerinin Algoritmalarında Aşırı Sorunlar (Rusça), Kişinu, Moldova: Ştiinţa .