Trapezoid graph (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/TrapezoidGraphFigure2.jpg?width=300 |
| dbo:wikiPageExternalLink | http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description%23description |
| dbo:wikiPageID | 31675608 (xsd:integer) |
| dbo:wikiPageLength | 10372 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1095244712 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Ron_Pinter dbc:Perfect_graphs dbr:Independent_set_(graph_theory) dbr:Martin_Charles_Golumbic dbr:Very-large-scale_integration dbr:Perfect_graph dbr:Graph_theory dbr:Intersection_graph dbr:Interval_graph dbr:Bipartite_graph dbc:Intersection_classes_of_graphs dbr:Trapezoid dbr:Permutation_graph dbr:Ido_Dagan dbr:File:TrapezoidGraphFigure2.jpg |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Perfect_graphs dbc:Intersection_classes_of_graphs |
| rdf:type | yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Communication100033020 yago:Graph107000195 yago:Group100031264 yago:WikicatIntersectionClassesOfGraphs yago:VisualCommunication106873252 yago:WikicatPerfectGraphs |
| 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 | freebase:Trapezoid graph yago-res:Trapezoid graph wikidata:Trapezoid graph dbpedia-es:Trapezoid graph dbpedia-ru:Trapezoid graph https://global.dbpedia.org/id/4wFZc |
| prov:wasDerivedFrom | wikipedia-en:Trapezoid_graph?oldid=1095244712&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/TrapezoidGraphFigure2.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Trapezoid_graph |
| is dbo:wikiPageWikiLink of | dbr:Ron_Pinter dbr:Perfect_graph dbr:Intersection_graph dbr:Interval_graph dbr:Polygon-circle_graph dbr:Permutation_graph |
| is foaf:primaryTopic of | wikipedia-en:Trapezoid_graph |
