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.

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

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.^[1] Egy másik alkalmazásuk a folytonos szakaszok megkeresése a DNS-térképek készítésénél.^[2]

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 ${\displaystyle \chi (G)=\omega (G)}$. Azt tudjuk, hogy ${\displaystyle \chi (G)\geq \omega (G)}$ ezért elég belátni, hogy ${\displaystyle \omega (G)\geq \chi (G)}$. Legyen ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle k}$ másik intervallumban. Ez azt jelentené, hogy van a gráfban ${\displaystyle k+1}$ méretű klikk, ami ellentmondás. (Hiszen ${\displaystyle \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.

1. Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch (2001). „A unified approach to approximating resource allocation and scheduling”. Journal of the ACM 48 (5), 1069–1090. o.
2. Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E. (1994). „An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA”. Bioinformatics 10 (3), 309–317. o.