La Teoría de las gráficas
Aplicaciones en la actualidad
Biología Molecular
modelos de proteínas
mapas genómicos
matemáticas y ciencias de la computación
generar nuevos algoritmos que efectúen simulaciones eficientes y que resuelvan problemas
diseño lógico, inteligencia artificial
construcción de robots basados en teoría de gráficas, álgebra lineal, estadística y geometría
sistemas operativos
lenguajes formales
gráficos por computadora
recuperación de información
la escritura de compiladores y la encriptación
estudio de las redes sociales, almacenamiento de datos en servidores
Química
fullerenos
modelado de las partículas de carbono
Área didáctica y lúdica
permite modelar y resolver juegos como el dominó, el juego Nim, come-solo, Torres de Hanoi
creación de laberintos con una estrecha relación entre la teoría de gráficas y la papiroflexia
Historia
Puentes de Königsberg, una de las 1eras gráficas, por Euler
Kirchhoff publicó leyes para calcular el voltaje y la corriente en circuitos eléctricos
Guthrie, colorea cualquier mapa de países con 4 colores, 2 vecinos nunca tengan el mismo color
Appel y Haken definieron términos y conceptos teóricos fundamentales de las gráficas
Caminos
Paseo, camino que no repite aristas, también llamado camino abierto
Trayectoria, un camino que no repite vértices
Ciclo, un camino cerrado en el que todos los vértices son diferentes excepto el vértice inicial
Conexividad, una gráfica G es conexa si en cada par de vértices existe un camino en la gráfica que los conecta.
Grafos
G=(v,e) donde v significa vértices y la e es de (edges, en inglés) pero para nosotros serían las aristas
Grafos simples, con vértices y aristas solamente
Gafos ponderados, donde las aristas ya tienen valores
Multigrafos, donde existen varios caminos entre vértices
Grafos dirigidos, donde se puede ir de A a B, pero de B a A no se puede
Grafos no dirigidos, no cuentan con una dirección en específico
Árboles
Un árbol es una gráfica conexa que no tiene ciclos.
los árboles se usan en las ciencias de la computación para desglosar problemas complejos y representarlos mediante una estructura ramificada.
ejemplos de árboles
Árbol con raíz
Árboles libres, árboles sin raíz
Un árbol está compuesto de nodos o vértices y aristas, al primer nodo o vértice se le conoce como raíz, los nodos que le siguen son sus "hijos" y los últimos vértices serían las hojas
Árbol de Peso Mínimo
Algoritmo de Prim
árbol formado por aristas que sean consecutivos, pero que pesen menos, sin formar ciclos
Algoritmo de Kruskal
es un árbol que pese menos, no teniendo que estar consecutivos, sin formal ciclos, cubriendo todos los vértices.