Γράφος διαστημάτων: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Ρομπότ:Αυτόματη επισήμανση ορφανών άρθρων; διακοσμητικές αλλαγές |
μΧωρίς σύνοψη επεξεργασίας |
||
Γραμμή 1:
{{Ορφανό|ημερομηνία=Απριλίου 2010}}
[[Αρχείο:Interval graph.svg|thumb|300px|Επτά διαστήματα πάνω στην γραμμή των πραγματικών και το αντίστοιχο γράφημα διαστημάτων με επτά κορυφές.]]
Στην [[θεωρία γράφων]], ένα '''γράφημα διαστημάτων''' είναι το [[γράφημα τομών]] μίας οικογένειας [[Διάστημα (μαθηματικά)|διαστημάτων]] πάνω στον χώρο των πραγματικών αριθμών. Έχει μία [[Κορυφή (Γραφοθεωρία)|κορυφή]] για κάθε διάστημα στην οικογένεια διαστημάτων και μία [[Ακμή (Γραφοθεωρία)|ακμή]] μεταξύ κάθε ζεύγους κορυφών που αντιστοιχούν σε διαστήματα των οποίων η τομή είναι μη κενή.
Τυπικότερα, ας είναι
Γραμμή 10:
:<math> \{I_\alpha, I_\beta\} \in E \iff I_\alpha \cap I_\beta \neq \emptyset. </math>
Τα γραφήματα διαστημάτων είναι χρήσιμα στην μοντελοποίηση [[Κατανομή πόρων|κατανομής πόρων]] στην [[επιχειρησιακή έρευνα]]. Κάθε διάστημα αντιπροσωπεύει ένα αίτημα δέσμευσης ενός πόρου για μία συγκεκριμένη χρονική περίοδο. Το πρόβλημα μεγίστου βάρους [[Ανεξάρτητο σύνολο|ανεξάρτητου συνόλου]] για το γράφημα αναπαριστά την εύρεση
Επίσης, η εύρεση οικογένειας διαστημάτων που αναπαριστούν ένα γράφημα διαστημάτων, μπορεί να να χρησιμοποιηθεί ως τρόπος σύνθεσης παρακείμενων υπακολουθιών στην χαρτογράφηση του [[DNA]] {{ref_label | Zang1994 | 2 | a}}.
Τα γραφήματα διαστημάτων είναι [[Χορδικό γράφημα|χορδικά γραφήματα]] και επομένως [[Τέλειο γράφημα|τέλεια γραφήματα]]. Τα [[συμπληρωματικό γράφημα|συμπληρώματά]] τους είναι [[συγκριτικά γραφήματα]] και
====Υποσημειώσεις====
| |||