Teoría de grafos extremales

tipo de documento Articulo Wikipedia Definición

Equipo Didactalia

Me gusta 0
Visitas 14
Comentarios 0
Guardar en
Acciones
- Enviar enlace

Acerca de este recurso...

Teoría de grafos extremales

Definición

Artículo WikipediaFuente Dbpedia

La teoría de grafos extremales es una rama del campo matemático de la teoría de grafos.La Teoría de grafos extremales estudia los grafos extremales ( máximos o mínimos) que satisfacen una determinada propiedad. La extremalidad puede ser tomada con respecto a diferentes invariantes de los grafos, tales como el orden , el tamaño o el grosor. Más abstractamente, estudia cómo las propiedades globales de un grafo influyen en las subestructuras locales del grafo. Por ejemplo , una pregunta simple de la teoría de grafos extremales es "¿Cuáles grafos acíclicos de n vértices tienen el máximo número de aristas?". Los grafos extremales de esta pregunta son los árboles de “n” vértices ,los cuales tienen n − 1 aristas . En términos más generales , una pregunta típica es la siguiente: dada una propiedad “P” del grafo, una invariante “u” y un conjunto “H” de grafos , queremos encontrar el valor mínimo de “m” tal que cada grafo en “H” tenga un “u” mayor que el “m” que posee la propiedad “P”. En el ejemplo anterior , “H” era el conjunto de los grafos de “n”- vértice, “P” era la propiedad de ser cíclico y “u” era el número de aristas en el grafo . Por lo tanto, cada grafo de “n” vértices con más de n − 1 aristas debe contener un ciclo.Varios resultados fundamentales en la teoría de grafos extremales son preguntas de la forma antes mencionada . Por ejemplo, el problema de cuántas aristas puede tener un grafo de “n”- vértice antes que el contenga como subgrafo un clique de tamaño “k” es contestado por el teorema de Turán .Si en lugar de cliques la misma pregunta se hace para grafos multi-partitos , la respuesta es dada por el teorema de Erdős-Stone.

Wikipedia Inglés http://en.wikipedia.org/wiki/Extremal_graph_theory

Wikipedia Español http://es.wikipedia.org/wiki/Teor?a_de_grafos_extremales

Enlaces externos relacionado http://diestel-graph-theory.com/index.html/ http://www.renyi.hu/~miki/BerlinG.pdf