Intervallumgráf

A Wikipédiából, a szabad enciklopédiából

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.

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[szerkesztés | forrásszöveg szerkesztése]

Minden intervallumgráf perfekt.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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