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

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

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

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

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

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

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

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

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

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

Εφαρμογές

Οι γράφοι διαστημάτων είναι χρήσιμα στην μοντελοποίηση κατανομής πόρων στην επιχειρησιακή έρευνα. Κάθε διάστημα αντιπροσωπεύει ένα αίτημα δέσμευσης ενός πόρου για μία συγκεκριμένη χρονική περίοδο. Το πρόβλημα μεγίστου βάρους ανεξάρτητου συνόλου για τον γράφο αναπαριστά την εύρεση της καλύτερης υποοικογένειας διαστημάτων που μπορεί να ληφθεί χωρίς τα διαστήματα να τέμνονται.^[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. https://archive.org/details/sim_bioinformatics_1994-06_10_3/page/309.