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

Επτά διαστήματα πάνω στην γραμμή των πραγματικών και ο αντίστοιχος γράφος διαστημάτων με επτά κόμβους.

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

Μαθηματικός ορισμός

Έστω $I_{1},I_{2},\ldots ,I_{n}\subset \mathbb {R}$, $n$ διαστήματα στους πραγματικούς αριθμούς, δηλαδή $I_{k}=[x_{k},y_{k}]$ για κάποιους πραγματικούς αριθμούς $x_{k}<y_{k}$. Τότε, ο μη κατευθυνόμενος γράφος που αντιστοιχεί σε αυτά τα διαστήματα είναι ο $G=(V,E)$ όπου το σύνολο των κόμβων

$V=\{I_{1},I_{2},\ldots ,I_{n}\}$,

και το σύνολο των ακμών

$E=\left\{\{I_{\alpha },I_{\beta }\}:I_{\alpha }\cap I_{\beta }\neq \emptyset \right\}$,

δηλαδή υπάρχει ακμή μεταξύ των $I_{\alpha }$ και $I_{\beta }$ ανν η τομή τους δεν είναι κενή.

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

Εφαρμογές

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

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

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

Δείτε επίσης

• Πλήρης γράφος
• Επίπεδος γράφος