Taidemuseo-ongelma

Taidemuseo-ongelma on paljon tutkittu matemaattinen ongelma geometrian osa-alueelta. Ongelmassa tarkoituksena on selvittää pienin mahdollinen vartijoiden määrä, joka riittää vartioimaan mielivaltaista yhtenäisen $n$-kulmion $(n\in N)$ muotoista taidemuseota. Vartijoita kuvataan monikulmion sisään sijoitetuilla pisteillä $v_{n}$. Museon piste $v_{k}$ on vartioitu, kun jostakin pisteestä $v_{n}$ voidaan piirtää jana pisteeseen $v_{k}$ ilman, että jana leikkaa monikulmion sivuja. Museo on vartioitu, kun sen kaikki pisteet ovat vartioituja.

Chvátalin taidemuseoteoreema

Trianguloidusta monikulmiosta muodostetun verkon värittäminen kolmella värillä.

Kehittäjänsä Václav Chvátalin mukaan nimetty Chvátalin taidemuseoteoreema antaa ylärajan pienimmälle vartijoiden lukumäärälle, joka vaaditaan $n$-kulmion vartioimiseen. Teoreeman mukaan pienin tarvittava vartijoiden määrä on korkeintaan $n/3$. Joissakin tapauksissa tämä määrä on välttämätön, toisissa tapauksissa pienempikin vartijoiden määrä riittää. Chvatál itse julkaisi teoreemansa todistuksen vuonna 1975. Myöhemmin, vuonna 1978 Chvátalin taidemuseoteoreemaan esitti yksinkertaisemman todistuksen Steve Fisk.

Fiskin todistus lyhyesti

Fiskin todistus perustuu verkkoteoriaan ja on seuraavanlainen: Aluksi monikulmio jaetaan kolmioihin toisiaan leikkaamattomilla janoilla siten, että janojen päätepisteet ovat monikulmion kulmissa. Näin trianguloidusta monikulmiosta muodostuu verkko, jossa kolmioiden kärjet ovat verkon solmuja ja kolmioiden sivut kaaria. Verkon solmut väritetään kolmella eri värillä siten, että jokaisen kolmion kärjissä olevat solmut ovat keskenään eri väriset, ts. mitkään kaksi toisiinsa kaarella yhdistettyä solmua eivät ole samanväriset. Tällainen kolmiväritys on aina mahdollista tehdä kuvatulla tavalla muodostetusta verkosta. Tämä nähdään, kun muodostetaan verkko, jonka solmut ovat aiemman verkon kolmioiden sisällä ja kaaret yhdistävät aina vierekkäisten kolmioiden solmut toisiinsa. Näin syntynyt verkko on puu, jonka solmujen aste on korkeintaan 3. Väritys suoritetaan aloittamalla yhdestä kolmiosta ja siirtymällä puun oksia pitkin kolmiosta seuraavaan ja värittämällä seuraavan kolmion solmu viereisen kolmion solmujen värien perusteella. Koska puu ei ole syklinen, näin suoritetussa värityksessä ei synny ristiriitoja. Kun väritys on tehty, mitkä tahansa keskenään samanväriset solmut ovat mahdollisia paikkoja vartijoille, joilla koko monikulmio saadaan vartioitua. Kun valitaan sen väriset solmut, joita verkossa on vähiten, saadaan vartijoden lukumääräksi korkeintaan $n/3$.

Ongelman variaatiot

Esimerkki kolmiulotteisesta kappaleesta, jonka sisätilan vartiointiin ei riitä se, että jokaiseen kärkeen sijoitetaan vartija.

Taidemuseo-ongelmasta on lukuisia eri variaatioita. Museon vaatimuksia muuttamalla ongelman ratkaisut muuttuvat. On osoitettu, että museon, jonka kaikki kulmat ovat suoria, vartioimiseen riittää aina $n/4$ vartijaa. Museon ulkopuolen vartiointia on myös tutkittu. Mielivaltaisen n-kulmion ulkopuolen vartiointiin tarvittavien vartijoiden pienimmän lukumäärän yläraja on $n/2$. Ongelma mutkistuu, jos tutkitaan kolmiulotteisia museoita. Tällöin museon vartioimiseen ei aina riitä edes se, että museon jokaisessa kärjessä on vartija.

Aiheesta muualla

• Aggarwal, A.: The art gallery theorem: Its variations, applications, and algorithmic aspects. Ph.D. thesis, Johns Hopkins University, 1984. .

• O'Rourke, Joseph: Art Gallery Theorems and Algorithms. Oxford University Press, 1987. Teoksen verkkoversio. .

• Shermer, Thomas: Recent Results in Art Galleries, s. 1384–1399. Oxford University Press, 1992. Teoksen verkkoversio. .