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

γράφος όπου οι κόμβοι του αντιστοιχούν σε διαστήματα στον άξονα των πραγματικών αριθμών και υπάρχουν ακμές μεταξύ τους αν η τομή των διαστ
(Ανακατεύθυνση από Γράφημα διαστημάτων)

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

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

Μαθηματικός ορισμός Επεξεργασία

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

 ,

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

 ,

δηλαδή υπάρχει ακμή μεταξύ των   και   ανν η τομή τους δεν είναι κενή.

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

Εφαρμογές Επεξεργασία

Οι γράφοι διαστημάτων είναι χρήσιμα στην μοντελοποίηση κατανομής πόρων στην επιχειρησιακή έρευνα. Κάθε διάστημα αντιπροσωπεύει ένα αίτημα δέσμευσης ενός πόρου για μία συγκεκριμένη χρονική περίοδο. Το πρόβλημα μεγίστου βάρους ανεξάρτητου συνόλου για τον γράφο αναπαριστά την εύρεση της καλύτερης υποοικογένειας διαστημάτων που μπορεί να ληφθεί χωρίς τα διαστήματα να τέμνονται.[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.