Γράφος διαστημάτων: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ WPCleaner v1.33b - Fixed using Βικιπαίδεια:WikiProject Check Wikipedia (Επικεφαλίδες που ξεκινούν με τρία "=") |
μορφοποίηση |
||
Γραμμή 10:
:<math> \{I_\alpha, I_\beta\} \in E \iff I_\alpha \cap I_\beta \neq \emptyset. </math>
Τα γραφήματα διαστημάτων είναι χρήσιμα στην μοντελοποίηση [[Κατανομή πόρων|κατανομής πόρων]] στην [[επιχειρησιακή έρευνα]]. Κάθε διάστημα αντιπροσωπεύει ένα αίτημα δέσμευσης ενός πόρου για μία συγκεκριμένη χρονική περίοδο. Το πρόβλημα μεγίστου βάρους [[Ανεξάρτητο σύνολο|ανεξάρτητου συνόλου]] για το γράφημα αναπαριστά την εύρεση της καλύτερης υποοικογένειας διαστημάτων που μπορεί να ληφθεί χωρίς τα διαστήματα να τέμνονται
Επίσης, η εύρεση οικογένειας διαστημάτων που αναπαριστούν ένα γράφημα διαστημάτων, μπορεί να να χρησιμοποιηθεί ως τρόπος σύνθεσης παρακείμενων υπακολουθιών στην χαρτογράφηση του [[DNA]] {{ref_label | Zang1994 | 2 | a}}.▼
Τα γραφήματα διαστημάτων είναι [[Χορδικό γράφημα|χορδικά γραφήματα]] και επομένως [[Τέλειο γράφημα|τέλεια γραφήματα]]. Τα [[συμπληρωματικό γράφημα|συμπληρώματά]] τους είναι [[συγκριτικά γραφήματα]] και οι σχέσεις σύγκρισης είναι ακριβώς η διάταξη των διαστημάτων.▼
| author = Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch
| title = A unified approach to approximating resource allocation and scheduling
Γραμμή 26 ⟶ 19 :
| pages = 1069–1090
| url = http://portal.acm.org/citation.cfm?id=335410&coll=portal&dl=ACM
| doi = 10.1145/502102.502107}}</ref>
▲Επίσης, η εύρεση οικογένειας διαστημάτων που αναπαριστούν ένα γράφημα διαστημάτων, μπορεί να να χρησιμοποιηθεί ως τρόπος σύνθεσης παρακείμενων υπακολουθιών στην χαρτογράφηση του [[DNA]]
| author = Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E.
| title = An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA
Γραμμή 36 ⟶ 29 :
| year = 1994
| pages = 309–317
| doi = 10.1093/bioinformatics/10.3.309}}</ref>
▲Τα γραφήματα διαστημάτων είναι [[Χορδικό γράφημα|χορδικά γραφήματα]] και επομένως [[Τέλειο γράφημα|τέλεια γραφήματα]]. Τα [[συμπληρωματικό γράφημα|συμπληρώματά]] τους είναι [[συγκριτικά γραφήματα]] και οι σχέσεις σύγκρισης είναι ακριβώς η διάταξη των διαστημάτων.
==Αναφορές==
<references/>
[[Κατηγορία:Θεωρία γράφων]]
| |||