| dbo:abstract
|
- Στην θεωρία γράφων, ένα γράφημα διαστημάτων είναι το μίας οικογένειας διαστημάτων πάνω στον χώρο των πραγματικών αριθμών. Έχει μία για κάθε διάστημα στην οικογένεια διαστημάτων και μία μεταξύ κάθε ζεύγους κορυφών που αντιστοιχούν σε διαστήματα των οποίων η τομή είναι μη κενή. Τυπικότερα, ας είναι μία οικογένεια διαστημάτων. Τότε, το αντίστοιχο γράφημα διαστημάτων είναι το G = (V, E) όπου και Τα γραφήματα διαστημάτων είναι χρήσιμα στην μοντελοποίηση στην επιχειρησιακή έρευνα. Κάθε διάστημα αντιπροσωπεύει ένα αίτημα δέσμευσης ενός πόρου για μία συγκεκριμένη χρονική περίοδο. Το πρόβλημα μεγίστου βάρους για το γράφημα αναπαριστά την εύρεση της καλύτερης υποοικογένειας διαστημάτων που μπορεί να ληφθεί χωρίς τα διαστήματα να τέμνονται. Επίσης, η εύρεση οικογένειας διαστημάτων που αναπαριστούν ένα γράφημα διαστημάτων, μπορεί να να χρησιμοποιηθεί ως τρόπος σύνθεσης παρακείμενων υπακολουθιών στην χαρτογράφηση του DNA. Τα γραφήματα διαστημάτων είναι και επομένως . Τα τους είναι και οι σχέσεις σύγκρισης είναι ακριβώς η διάταξη των διαστημάτων. (el)
- Die Intervallgraphen bilden in der Graphentheorie eine spezielle Klasse von Graphen. Die erste Erwähnung findet man bei György Hajós 1957. Einen wesentlichen Schub bekam das Interesse an Intervallgraphen durch einen Vorstoß von Seymour Benzer 1959, der eine These zur Struktur von Genen überprüfen wollte. Zu den zeitgenössischen Anwendungen gehören unter anderem Probleme des Scheduling, archäologische Seriation, Verhaltenspsychologie, Temporallogik, Schaltungsdesign und das Human Genome Project. (de)
- En teoría de grafos, un grafo de intervalos es el grafo intersección de un multiconjunto de intervalos en la recta real. Cuenta con un vértice para cada intervalo en el conjunto, y una arista entre cada par de vértices correspondientes a los intervalos que se cruzan. (es)
- In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals. These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning. (en)
- En théorie des graphes, un graphe d'intervalles est le graphe d'intersection d'un ensemble d'intervalles de la droite réelle. Chaque sommet du graphe d'intervalles représente un intervalle de l'ensemble, et une arête relie deux sommets lorsque les deux intervalles correspondants s'intersectent. (fr)
- 区間グラフとは、グラフ理論のグラフの一種であり、区間集合の区間の重複を表すである。それぞれの区間が頂点に対応し、辺は区間同士の重複（交差）関係を表す。 (ja)
- Een intervalgraaf is een voorstelling in graafvorm van een verzameling van intervallen op de getallenlijn. Elke knoop in de graaf stelt een interval uit de verzameling voor, en twee knopen zijn verbonden door een kant indien de corresponderende intervallen elkaar geheel of gedeeltelijk overlappen. (nl)
- Nella teoria dei grafi, un grafo d'intervallo è il di un multiinsieme di intervalli sulla linea reale. Ha un solo vertice per ciascun intervallo dell'insieme, e uno spigolo tra ogni coppia di vertici corrispondenti agli intervalli che intersecano. (it)
- Интервальный граф — граф пересечений мультимножества интервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются. (ru)
- Graf przedziałowy – graf utworzony ze zbioru odcinków na prostej, poprzez przypisanie każdemu odcinkowi wierzchołka i połączenie krawędziami wierzchołków, których odcinki się nakładają. Formalnie, niech będzie zbiorem odcinków. Odpowiada mu graf przedziałowy G = (V, E), gdzie i Grafy przedziałowe są stosowane w modelowaniu alokacji zasobów w badaniach operacyjnych. Każdy przedział odpowiada wtedy zapotrzebowaniu na zasób przez jakiś czas. Znalezienie maksymalnego zbioru niezależnego odpowiada znalezieniu maksymalnego zbioru zapotrzebowań który może być zaspokojony bez stworzenie konfliktów. Grafy przedziałowe są grafami doskonałymi. (pl)
- Інтервальний граф — граф перетинів мультимножини інтервалів на прямій. Має по одній вершині для кожного інтервалу в множині і по ребру між кожною парою вершин, якщо відповідні інтервали перетинаються. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 20658 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:edition
| |
| dbp:mode
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Die Intervallgraphen bilden in der Graphentheorie eine spezielle Klasse von Graphen. Die erste Erwähnung findet man bei György Hajós 1957. Einen wesentlichen Schub bekam das Interesse an Intervallgraphen durch einen Vorstoß von Seymour Benzer 1959, der eine These zur Struktur von Genen überprüfen wollte. Zu den zeitgenössischen Anwendungen gehören unter anderem Probleme des Scheduling, archäologische Seriation, Verhaltenspsychologie, Temporallogik, Schaltungsdesign und das Human Genome Project. (de)
- En teoría de grafos, un grafo de intervalos es el grafo intersección de un multiconjunto de intervalos en la recta real. Cuenta con un vértice para cada intervalo en el conjunto, y una arista entre cada par de vértices correspondientes a los intervalos que se cruzan. (es)
- En théorie des graphes, un graphe d'intervalles est le graphe d'intersection d'un ensemble d'intervalles de la droite réelle. Chaque sommet du graphe d'intervalles représente un intervalle de l'ensemble, et une arête relie deux sommets lorsque les deux intervalles correspondants s'intersectent. (fr)
- 区間グラフとは、グラフ理論のグラフの一種であり、区間集合の区間の重複を表すである。それぞれの区間が頂点に対応し、辺は区間同士の重複（交差）関係を表す。 (ja)
- Een intervalgraaf is een voorstelling in graafvorm van een verzameling van intervallen op de getallenlijn. Elke knoop in de graaf stelt een interval uit de verzameling voor, en twee knopen zijn verbonden door een kant indien de corresponderende intervallen elkaar geheel of gedeeltelijk overlappen. (nl)
- Nella teoria dei grafi, un grafo d'intervallo è il di un multiinsieme di intervalli sulla linea reale. Ha un solo vertice per ciascun intervallo dell'insieme, e uno spigolo tra ogni coppia di vertici corrispondenti agli intervalli che intersecano. (it)
- Интервальный граф — граф пересечений мультимножества интервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются. (ru)
- Інтервальний граф — граф перетинів мультимножини інтервалів на прямій. Має по одній вершині для кожного інтервалу в множині і по ребру між кожною парою вершин, якщо відповідні інтервали перетинаються. (uk)
- Στην θεωρία γράφων, ένα γράφημα διαστημάτων είναι το μίας οικογένειας διαστημάτων πάνω στον χώρο των πραγματικών αριθμών. Έχει μία για κάθε διάστημα στην οικογένεια διαστημάτων και μία μεταξύ κάθε ζεύγους κορυφών που αντιστοιχούν σε διαστήματα των οποίων η τομή είναι μη κενή. Τυπικότερα, ας είναι μία οικογένεια διαστημάτων. Τότε, το αντίστοιχο γράφημα διαστημάτων είναι το G = (V, E) όπου και Επίσης, η εύρεση οικογένειας διαστημάτων που αναπαριστούν ένα γράφημα διαστημάτων, μπορεί να να χρησιμοποιηθεί ως τρόπος σύνθεσης παρακείμενων υπακολουθιών στην χαρτογράφηση του DNA. (el)
- In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals. (en)
- Graf przedziałowy – graf utworzony ze zbioru odcinków na prostej, poprzez przypisanie każdemu odcinkowi wierzchołka i połączenie krawędziami wierzchołków, których odcinki się nakładają. Formalnie, niech będzie zbiorem odcinków. Odpowiada mu graf przedziałowy G = (V, E), gdzie i Grafy przedziałowe są stosowane w modelowaniu alokacji zasobów w badaniach operacyjnych. Każdy przedział odpowiada wtedy zapotrzebowaniu na zasób przez jakiś czas. Znalezienie maksymalnego zbioru niezależnego odpowiada znalezieniu maksymalnego zbioru zapotrzebowań który może być zaspokojony bez stworzenie konfliktów. (pl)
|
| rdfs:label
|
- Intervallgraph (de)
- Γράφημα διαστημάτων (el)
- Grafo de intervalos (es)
- Interval graph (en)
- Graphe d'intervalles (fr)
- Grafo d'intervallo (it)
- 区間グラフ (ja)
- Graf przedziałowy (pl)
- Intervalgraaf (nl)
- Интервальный граф (ru)
- Інтервальний граф (uk)
|
| owl:differentFrom
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is owl:differentFrom
of | |
| is foaf:primaryTopic
of | |
