Ramme graf

I grafteori er en rammegraf en slags ikke- rettet graf , der kan tegnes på et plan på en sådan måde, at enhver afgrænset flade er en firkant , og ethvert toppunkt med tre eller færre naboer falder ind på en ubegrænset flade.

Relaterede grafklasser

Rammegrafer inkluderer, som særlige tilfælde , træer , gitter , tandhjul og polyominografer .

Da boksgrafer er plane , er de også median , hvilket betyder, at der for alle tre spidser u , v og w er et enkelt toppunkt m ( u , v , w ) (kaldet medianen), der ligger på den korteste vej mellem hvert par af disse tre hjørner [1] . Som med mere generelle mediangrafer er boksgrafer delvise terninger  - deres hjørner kan mærkes med bitstrenge , således at Hamming-afstanden mellem strenge er lig med den korteste afstand mellem hjørner.

Karakteristika

Boksgrafer kan karakteriseres på flere andre måder end planaritetsegenskaben [2] :

• De er mediangrafer , der ikke indeholder noget medlem af den uendelige familie af forbudte grafer som en genereret undergraf . Disse forbudte grafer inkluderer en terning ( simplex graf K 3 ), et direkte produkt af en kant og en klo K 1,3 (klo simplex graf) og grafer dannet ud fra et tandhjul ved at tilføje et ekstra toppunkt forbundet med en kant til midten af ​​hjulet.
• De er forbundne og todelte grafer sådan, at hvis et hvilket som helst toppunkt r vælges som rod , har et hvilket som helst toppunkt højst to naboer, der er tættere på r , og sådan at for ethvert toppunkt v bundtet af v (grafen bestående af toppunkter for hver indfaldende v kanter og kanter for alle cyklusser af længde 4 indeholdende toppunkt v ) er enten en cyklus med længde på mindst tre eller et adskilt sæt stier.
• De er to grafer af linjekonfigurationer på det hyperbolske plan , der ikke indeholder tre parvis skærende linjer.

Algoritmer

At beskrive boksgrafer i form af afstand fra rod- og toppunktsbundterne (se ovenfor) kan bruges i forbindelse med bredde-først-søgning som en del af en lineær-tidsalgoritme for at teste, om en given graf er en kassegraf uden at skulle bruge mere komplekse lineære-tidsalgoritmer til at kontrollere planariteten af ​​vilkårlige grafer [2] .

Nogle algoritmiske problemer på rammegrafer kan løses mere effektivt end de samme problemer på mere generelle plane grafer. For eksempel foreslog Chepoy, Dragan, Waxes og Fancillini [3] [4] tidslineære algoritmer til beregning af diameteren af ​​kassegrafer og til at finde det toppunkt, der er i minimumsafstanden til alle andre toppunkter (det vil sige toppunktet hvorved minimum af den maksimale afstand til alle andre hjørner).

Noter

1. ↑ Soltan, Zambitsky, Prisakaru, 1973 . Se Peterin, 2006 for en mere generel diskussion af plane mediangrafer .
2. ↑ 1 2 Bandelt, Chepoi, Eppstein, 2010 .
3. ↑ Chepoi, Dragan, Vaxès, 2002 .
4. ↑ Chepoi, Fanciullini, Vaxès, 2004 .

Litteratur

• H.J. Bandelt, V. Chepoi, D. Eppstein. Kombinatorik og geometri af endelige og uendelige kvadratgrafer // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , no. 4 . - S. 1399-1440 . - doi : 10.1137/090760301 . - arXiv : 0905.4537 .
• V. Chepoi, F. Dragan, Y. Vaxes. Proc. 13. år. ACM–SIAM Symp. om diskrete algoritmer (SODA 2002). - 2002. - S. 346-355 .
• V. Chepoi, C. Fanciullini, Y. Vaxès. Medianproblem i nogle plantrianguleringer og kvadranguleringer // Comput. Geom.. - 2004. - V. 27 , no. 3 . - S. 193-210 . - doi : 10.1016/j.comgeo.2003.11.002 .
• I. Peterin. En karakterisering af plane mediangrafer // Diskussioner Mathematicae Graph Theory. - 2006. - T. 26 . - S. 41-48 .  (utilgængeligt link)
• Soltan P. S., Zambitsky D. K., Prisacaru K. F. Ekstreme problemer på grafer og algoritmer til deres løsning. - Chişinǎu, Moldova: Shtiintsa, 1973.