Teoría de Grafos

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
Teoría de Grafos por Mind Map: Teoría de Grafos

1. Historia

1.1. Aunque la primera publicación de teoría de gráficas data de 1736 (vea el ejemplo 8.2.16) y varios resultados importantes de teoría de gráficas se obtuvieron en el siglo XIX, no fue sino hasta 1920 que surgió un interés sostenido, amplio e intenso en la teoría de gráficas. En realidad, el primer libro de texto de este tema ([König]) apareció en 1936. Sin duda, una de las razones del reciente interés en la teoría de gráficas es su aplicabilidad en muchos campos, incluyendo ciencias de la computación, química, investigación de operaciones, ingeniería eléctrica, lingüística y economía.

2. Definiciones

2.1. Una gráfica (o gráfica no dirigida) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se asocia con un par no ordenado de vértices. Si existe una arista única e asociada con los vértices u y w, se escribe e = (v, w) o e = (w, v). En este contexto, (v, w) denota una arista entre v y w en una gráfica no dirigida y no es un par ordenado.

2.2. Una gráfica dirigida (o digráfica) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tales que cada arista e ∈ E está asociada con un par ordenado de vértices. Si hay una arista única e asociada con el par ordenado (v, w) de vértices, se escribe e = (v, w), que denota una arista de v a w.

3. Tipos de Grafos

3.1. 1. Simples 2.Completos 3. Bipartidos 4. Planos 5. Conexos 6.Ponderado

4. Aplicaciones

4.1. Número de Bacon, Gráficas de Similitud, El Cubo-n (hipercubo), Determinar la Ruta más Corta