| dbo:abstract
|
- En teoría de grafos, los grafos trapezoidales son grafos de intersección de trapezoides entre dos líneas horizontales. Son una clase de grafos co-comparables que contienen como subclases a los y a los . Se dice que tenemos un grafo trapezoidal, si existe un conjunto de trapezoides que se correspondan a los vértices del grafo que cumplan que dos vértices están unidos por una arista si y solo si los trapezoides correspondientes a los mismos se intersecan. Los grafos trapezoidales fueron introducidos por , , y en 1968. Existen algoritmos de para calcular su número cromático, su Conjunto independiente con costo(conjunto independiente ponderado), cobertura de clique(número de clique) y clique de costo máximo. (es)
- In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by , Golumbic, and Pinter in 1988. There exists algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique. (en)
- В теории графов трапецеидальными графами называются графы пересечений трапеций, все параллельные стороны которых лежат на двух прямых. Этот класс графов содержится в классе графов косравнимости и содержат интервальные графы и графы перестановки в качестве подклассов. Граф является трапецеидальным в том и только в том случае, когда существует набор трапеций, соответствующих вершинам графа, и две вершины графа соединены ребром в том и только в том случае, когда соответствующие вершинам трапеции пересекаются. Трапецеидальные графы были введены в рассмотрение в 1988 году Даганом (Ido Dagan), Колумбиком (Martin Charles Golumbic) и Пинтером (Ron Pinter). Для этих графов существуют алгоритмы со временем работы для раскраски графа, для поиска взвешенных независимых множеств, кликовых покрытий и максимальных взвешенных клик. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10372 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En teoría de grafos, los grafos trapezoidales son grafos de intersección de trapezoides entre dos líneas horizontales. Son una clase de grafos co-comparables que contienen como subclases a los y a los . Se dice que tenemos un grafo trapezoidal, si existe un conjunto de trapezoides que se correspondan a los vértices del grafo que cumplan que dos vértices están unidos por una arista si y solo si los trapezoides correspondientes a los mismos se intersecan. Los grafos trapezoidales fueron introducidos por , , y en 1968. Existen algoritmos de para calcular su número cromático, su Conjunto independiente con costo(conjunto independiente ponderado), cobertura de clique(número de clique) y clique de costo máximo. (es)
- In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by , Golumbic, and Pinter in 1988. There exists algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique. (en)
- В теории графов трапецеидальными графами называются графы пересечений трапеций, все параллельные стороны которых лежат на двух прямых. Этот класс графов содержится в классе графов косравнимости и содержат интервальные графы и графы перестановки в качестве подклассов. Граф является трапецеидальным в том и только в том случае, когда существует набор трапеций, соответствующих вершинам графа, и две вершины графа соединены ребром в том и только в том случае, когда соответствующие вершинам трапеции пересекаются. Трапецеидальные графы были введены в рассмотрение в 1988 году Даганом (Ido Dagan), Колумбиком (Martin Charles Golumbic) и Пинтером (Ron Pinter). Для этих графов существуют алгоритмы со временем работы для раскраски графа, для поиска взвешенных независимых множеств, кликовых покрытий и м (ru)
|
| rdfs:label
|
- Grafo trapezoidal (es)
- Трапецеидальный граф (ru)
- Trapezoid graph (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
