| Property |
Value |
| dbo:abstract
|
- En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. Los grafos perfectos incluyen varias familias de grafos importantes, y sirven para unificar resultados relacionados con la coloración y los cliques en esas familias. Por ejemplo, en todos los grafos perfectos, el problema de coloración de grafos, el y el pueden ser resueltos en tiempo polinómico (). Además, varios teoremas min-max importantes de combinatoria como el , pueden ser expresados en términos de la perfección de ciertos grafos asociados. La teoría de grafos perfectos fue desarrollada a partir de un resultado obtenido en 1958 por que en lenguaje moderno puede ser interpretado de modo que el complementario de un grafo bipartito es perfecto. Este resultado puede ser visto también como un equivalente simple del teorema de König, un resultado anterior que relaciona emparejamientos con cobertura de vértices en grafos bipartitos. El primer uso de la frase "grafo perfecto" parece estar en un paper de 1963 publicado por Claude Berge. En este paper, Berge unió el resultado de Gallai con varios otros resultados similares, definiendo los grafos perfectos y conjeturando una caracterización de esos grafos que luego fue probado como el Teorema fuerte de los grafos perfectos. (es)
- En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. Los grafos perfectos incluyen varias familias de grafos importantes, y sirven para unificar resultados relacionados con la coloración y los cliques en esas familias. Por ejemplo, en todos los grafos perfectos, el problema de coloración de grafos, el y el pueden ser resueltos en tiempo polinómico (). Además, varios teoremas min-max importantes de combinatoria como el , pueden ser expresados en términos de la perfección de ciertos grafos asociados. La teoría de grafos perfectos fue desarrollada a partir de un resultado obtenido en 1958 por que en lenguaje moderno puede ser interpretado de modo que el complementario de un grafo bipartito es perfecto. Este resultado puede ser visto también como un equivalente simple del teorema de König, un resultado anterior que relaciona emparejamientos con cobertura de vértices en grafos bipartitos. El primer uso de la frase "grafo perfecto" parece estar en un paper de 1963 publicado por Claude Berge. En este paper, Berge unió el resultado de Gallai con varios otros resultados similares, definiendo los grafos perfectos y conjeturando una caracterización de esos grafos que luego fue probado como el Teorema fuerte de los grafos perfectos. (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:author
|
- Golumbic, Martin Charles (es)
- Golumbic, Martin Charles (es)
|
| prop-es:authorlink
|
- László Lovász (es)
- Martin Charles Golumbic (es)
- László Lovász (es)
- Martin Charles Golumbic (es)
|
| prop-es:autor
| |
| prop-es:año
|
- 1958 (xsd:integer)
- 1961 (xsd:integer)
- 1972 (xsd:integer)
- 2005 (xsd:integer)
- 2006 (xsd:integer)
|
| prop-es:doi
|
- 101007 (xsd:integer)
- 101016 (xsd:integer)
|
| prop-es:enlaceautor
|
- László Lovász (es)
- Claude Berge (es)
- Tibor Gallai (es)
- László Lovász (es)
- Claude Berge (es)
- Tibor Gallai (es)
|
| prop-es:fechaacceso
| |
| prop-es:fechaarchivo
| |
| prop-es:first
|
- Martin (es)
- László (es)
- Alexander (es)
- Martin (es)
- László (es)
- Alexander (es)
|
| prop-es:id
|
- ISBN 0-444-51530-5 (es)
- ISBN 0-444-51530-5 (es)
|
| prop-es:last
|
- Lovász (es)
- Grötschel (es)
- Schrijver (es)
- Lovász (es)
- Grötschel (es)
- Schrijver (es)
|
| prop-es:número
| |
| prop-es:publicación
| |
| prop-es:publisher
|
- Springer-Verlag (es)
- Academic Press (es)
- Springer-Verlag (es)
- Academic Press (es)
|
| prop-es:páginas
|
- 51 (xsd:integer)
- 95 (xsd:integer)
- 114 (xsd:integer)
- 143 (xsd:integer)
- 253 (xsd:integer)
- 395 (xsd:integer)
|
| prop-es:title
|
- Algorithmic Graph Theory and Perfect Graphs (es)
- Geometric Algorithms and Combinatorial Optimization (es)
- Algorithmic Graph Theory and Perfect Graphs (es)
- Geometric Algorithms and Combinatorial Optimization (es)
|
| prop-es:título
|
- A characterization of perfect graphs (es)
- Normal hypergraphs and the perfect graph conjecture (es)
- Maximum-minimum Sätze über Graphen (es)
- Recognizing Berge graphs (es)
- The strong perfect graph theorem (es)
- Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (es)
- A characterization of perfect graphs (es)
- Normal hypergraphs and the perfect graph conjecture (es)
- Maximum-minimum Sätze über Graphen (es)
- Recognizing Berge graphs (es)
- The strong perfect graph theorem (es)
- Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (es)
|
| prop-es:url
| |
| prop-es:urlarchivo
| |
| prop-es:volumen
|
- 2 (xsd:integer)
- 9 (xsd:integer)
- 10 (xsd:integer)
- 13 (xsd:integer)
- 25 (xsd:integer)
- 164 (xsd:integer)
|
| prop-es:year
|
- 1980 (xsd:integer)
- 1988 (xsd:integer)
|
| dct:subject
| |
| rdfs:comment
|
- En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. (es)
- En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. (es)
|
| rdfs:label
|
- Grafo perfecto (es)
- Grafo perfecto (es)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
