Γράφημα διαστημάτων

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Επτά διαστήματα πάνω στην γραμμή των πραγματικών και το αντίστοιχο γράφημα διαστημάτων με επτά κορυφές.

Στην θεωρία γράφων, ένα γράφημα διαστημάτων είναι το γράφημα τομών μίας οικογένειας διαστημάτων πάνω στον χώρο των πραγματικών αριθμών. Έχει μία κορυφή για κάθε διάστημα στην οικογένεια διαστημάτων και μία ακμή μεταξύ κάθε ζεύγους κορυφών που αντιστοιχούν σε διαστήματα των οποίων η τομή είναι μη κενή.

Τυπικότερα, ας είναι

I_1, I_2, \ldots, I_n \subset R

μία οικογένεια διαστημάτων. Τότε, το αντίστοιχο γράφημα διαστημάτων είναι το G = (V, E) όπου

 V = \{I_1, I_2, \ldots, I_n\}

και

 \{I_\alpha, I_\beta\} \in E \iff  I_\alpha \cap I_\beta \neq \emptyset.

Τα γραφήματα διαστημάτων είναι χρήσιμα στην μοντελοποίηση κατανομής πόρων στην επιχειρησιακή έρευνα. Κάθε διάστημα αντιπροσωπεύει ένα αίτημα δέσμευσης ενός πόρου για μία συγκεκριμένη χρονική περίοδο. Το πρόβλημα μεγίστου βάρους ανεξάρτητου συνόλου για το γράφημα αναπαριστά την εύρεση της καλύτερης υποοικογένειας διαστημάτων που μπορεί να ληφθεί χωρίς τα διαστήματα να τέμνονται [ 1 ].

Επίσης, η εύρεση οικογένειας διαστημάτων που αναπαριστούν ένα γράφημα διαστημάτων, μπορεί να να χρησιμοποιηθεί ως τρόπος σύνθεσης παρακείμενων υπακολουθιών στην χαρτογράφηση του DNA [ 2 ].

Τα γραφήματα διαστημάτων είναι χορδικά γραφήματα και επομένως τέλεια γραφήματα. Τα συμπληρώματά τους είναι συγκριτικά γραφήματα και οι σχέσεις σύγκρισης είναι ακριβώς η διάταξη των διαστημάτων.

Υποσημειώσεις[Επεξεργασία | επεξεργασία κώδικα]

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. doi:10.1145/502102.502107. http://portal.acm.org/citation.cfm?id=335410&coll=portal&dl=ACM. 

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. doi:10.1093/bioinformatics/10.3.309.