Intervallumgráf

Hét intervallum a valós számegyenesen és a hozzájuk tartozó hét csúcspontú intervallumgráf.

A gráfelméletben az intervallumgráf olyan gráf, aminek a pontjai megfeleltethetőek a valós számok egy-egy intervallumának, és két pontja között pontosan akkor van él, ha a megfelelő intervallumok metszete nem üres – tehát intervallumok metszetgráfja.

Az operációkutatásban az intervallumgráfokat erőforráskiosztási problémák modellezésére használják. Az intervallumok jelzik az egyes kérelmek időtartamát; a legnagyobb súlyú független ponthalmaz felel meg az optimális kiosztásnak. Egy másik alkalmazásuk a folytonos szakaszok megkeresése a DNS-térképek készítésénél.

Tétel

Minden intervallumgráf perfekt.

Bizonyítás

Intervallumgráfoknak feszített részgráfjai is intervallumgráfok, tehát elég belátni, hogy minden intervallumgráfra $\chi (G)=\omega (G)$. Azt tudjuk, hogy $\chi (G)\ge \omega (G)$ ezért elég belátni, hogy $\omega (G)\ge \chi (G)$. Legyen $\omega (G)=k$. Színezzük az intervallumokat bal végpontjuk szerint, balról jobbra, a legelső színnel, ami nem mond ellent a korábbi intervallumok színezésének (ez tehát a mohó algoritmus használata). Ha a $k+1$-edik színt kellene használnunk valamelyik intervallum színezéséhez, az azt jelentené, hogy ennek az intervallumnak q bal oldali végpontja benne van $k$ másik intervallumban. Ez azt jelentené, hogy van a gráfban $k+1$ méretű klikk, ami ellentmondás. (Hiszen $\omega (G)=k$, azaz a legnagyobb klikk mérete k).

Hivatkozások

• Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 83.