Teoría de grafos extremales

tipo de documento Articolo di Wikipedia DbpediaThing

Equipo Didactalia

Mi piace 0
Visite 14
Commenti 0
Salva su
Azioni
- Invia link

Info su questa risorsa...

Teoría de grafos extremales

DbpediaThing

Artículo WikipediaFuente Dbpedia

Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal (maximal or minimal) graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth. More abstractly, it studies how global properties of a graph influence local substructures of the graph.For example, a simple extremal graph theory question is "which acyclic graphs on n vertices have the maximum number of edges?" The extremal graphs for this question are trees on n vertices, which have n − 1 edges. More generally, a typical question is the following. Given a graph property P, an invariant u, and a set of graphs H, we wish to find the minimum value of m such that every graph in H which has u larger than m possess property P. In the example above, H was the set of n-vertex graphs, P was the property of being cyclic, and u was the number of edges in the graph. Thus every graph on n vertices with more than n − 1 edges must contain a cycle.Several foundational results in extremal graph theory are questions of the above-mentioned form. For instance, the question of how many edges can an n-vertex graph have before it must contain as subgraph a clique of size k is answered by Turán's theorem. Instead of cliques, if the same question is asked for complete multi-partite graphs, the answer is given by the Erdős–Stone theorem.

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