Intervallumgráf
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ac/Interval_graph.svg/300px-Interval_graph.svg.png)
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 . Azt tudjuk, hogy ezért elég belátni, hogy . Legyen . 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 -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 másik intervallumban. Ez azt jelentené, hogy van a gráfban méretű klikk, ami ellentmondás. (Hiszen , 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.