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

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

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

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

και

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

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

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

Αναφορές

Θεωρία γράφων