PROFILPELAJAR.COM

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.^[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 $\chi (G)=\omega (G)$ . Azt tudjuk, hogy $\chi (G)\geq \omega (G)$ ezért elég belátni, hogy $\omega (G)\geq \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.

↑ 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.
↑ 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.