Teoría de las gráficas

Teoría de las gráficas

1. Se considera que tiene su inicio en 1736 cuando Leonhard Euler publicó Solutio problematis and geometrian situs pertinentis en donde aparece la solución al famoso Problema de los Puentes de Königsberg. Durante el siglo XIX la Teoría de las Gráficas fue redescubierta a través del estudio de diversos problemas obteniendo así nuevos y más resultados importantes

   • Aplicaciones en la actualidad:Las gráficas (o grafos como los llaman en otros países) tienen una gran cantidad de aplicaciones y se utilizan en muchas áreas de la ciencia (química, computación, biología, sociología, etc.). Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos, Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de programas (PERT) . Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos). Se usa para la solución de problemas de genética y problemas de automatización de la proyección

2. El Grafo: Es una composición de un conjunto de objetos conocidos como nodos que se relacionan con otros nodos a través de un conjunto de conexiones conocidas como aristas. Los grafos permiten estudiar las relaciones que existen entre unidades que interactúan con otras

   • A partir de esta figura se definen los siguientes elementos:
     • Vértices (nodos) Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a, b, c, d}. Lados (ramas o aristas) Son las líneas que unen un vértice con otro y se les asigna una letra, un numero o una combinación de ambos. En el grafo anterior los lados son: L= {1, 2, 3, 4, 5, 6}. Lados paralelos Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P= {2,3}. Lazo Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A= {6} Valencia de un vértice Es el número de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son: Valencia (a)=2 Valencia (c)=2 Valencia (b)=4 Valencia (d)=3
   • Tipos de grafos Grafo dirigido Un grafo dirigido conocido también como dígrafo consta de un conjunto de vértices y aristas donde cada arista se asocia de forma unidireccional a través de una flecha con otro. Las aristas dependiendo de su salida o ingreso reciben la calificación de entrante o saliente, la condición común, es que siempre tienen un destino hacia un nodo. Grafo no dirigido Los grafos no dirigidos son aquellos que constan un conjunto de vértices que están conectados a un conjunto de aristas de forma no direccional. Esto significa que una arista puede indistintamente recorrerse desde cualquiera de sus puntos y en cualquier dirección. Grafos etiquetados Esta clasificación es denominada como grafos etiquetados o grafos dirigidos con pesos. Este tipo de grafos concentran aristas que pueden poseer información adicional donde podemos reflejar nombres, costos, valores u otros datos. Estos grafos también son denominados como redes de actividad y el número asociado al arco, se le d
   • Características de los grafos Grafos simples Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Grafos conexos Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
   • Grafos completos Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente Ⱪ, siendo Ⱪn el grafo completo de n vértices. Un Ⱪn, es decir, grafo completo de n vértices tiene exactamente (n(n-1))/2 aristas. La representación gráfica de los Ⱪn como los vértices de un polígono regular da cuenta de su peculiar estructura. Grafos bipartitos Un grafo G es bipartito si puede expresarse como G={V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones: Cada arista de A une un vértice de V1 con uno de V2 . No existen aristas uniendo dos elementos de V1 ; análogamente para V2 . Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejerc

3. Caminos: Es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Un camino simple es aquel que no repite vértices en su recorrido. Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último.

   • Camino euleriano Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Si existe tal camino decimos que el grafo es euleriano. Esta definición es dual a la de camino hamiltoniano.
   • Camino hamiltoniano Existe un concepto dual al de camino/ciclo Euleriano. Un camino hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez.

4. Árboles: Un árbol es una gráfica conexa sin ciclos. En general nos referimos a una gráfica sin ciclos como acíclica. Es importante hacer notar que al no tener ciclos, toda arista en un árbol es un puente. Si relajamos la condición de la conexidad, el concepto de árbol puede extenderse de la siguiente manera: un bosque es una gráfica sin ciclos (puede o no ser conexa). Si tenemos un bosque no conexo, entonces se sigue que sus componentes conexas son árboles.

   • Componentes de un árbol Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz, además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc
     • COMPONENTES DE UN ÁRBOL: Nodo padre, nodo hijo, hermano, nodo raíz, nodo hoja, nodo interior, orden, grado,, nivel, rama, altura, peso
   • Un árbol de peso mínimo es aquel que obtenemos en un grafo conexo y sin ciclos. Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas es mínima.
     • Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo. En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad

Images and files in the map