Fundamentos de Teoría de Grafos: Conceptos, Teoremas y Algoritmos Clave
Enviado por Chuletator online y clasificado en Matemáticas
Escrito el en 
español con un tamaño de 3,83 KB
1. Explica con claridad los siguientes pares de conceptos, dejando claro si hay alguna relación entre ellos:
a) Grafo recorrible y grafo de Euler
Un grafo es de Euler si él mismo es un bucle de Euler, esto es, existe un bucle donde se pasa por cada arista del grafo exactamente una vez. Un grafo es recorrible si existe un camino abierto tal que pasa por cada arista del grafo exactamente una vez. Los primeros se pueden caracterizar como los grafos conexos con todos los vértices de grado par y los segundos como los grafos conexos con exactamente dos vértices de grado impar. Por tanto, si es recorrible no puede ser de Euler y viceversa. Si el grafo es recorrible, quitando o poniendo la arista que une los dos vértices de grado impar, se obtiene otro grafo de Euler.
b) Ciclo y bucle de un grafo
Un bucle en un grafo es un camino cerrado, esto es, que empieza y termina en el mismo vértice. Un ciclo es un bucle donde solo se repite el vértice de inicio. Todo ciclo es un bucle, pero no al revés.
c) Árbol y subgrafo economía de un grafo
Un árbol es un grafo conexo sin ciclos. El subgrafo economía de un grafo conexo G con aristas ponderadas con un número o peso es un subgrafo conexo de G que contiene todos los vértices de G y con el menor coste posible, esto es, la suma de los pesos de las aristas es mínima. Todo subgrafo economía es un árbol porque puedo “quitar” los ciclos que haya si elimino una arista.
d) Grafo conexo y componente conexa de un grafo
Un grafo es conexo si todo par de vértices están conectados, esto es, hay un camino de uno a otro. Una componente conexa de un grafo G es un subgrafo conexo de G que no está contenido en ningún otro subgrafo conexo de G. Toda componente conexa es un grafo conexo, pero lo contrario no es cierto (se debería dar un ejemplo).
2. Enuncia con precisión y detalle los siguientes resultados:
a) Teorema de caracterización de grafos de Euler
Todo grafo G es de Euler si y solo si G es conexo y todo vértice es de grado par.
b) Teorema de las aristas y los grados de los vértices de un grafo
La suma de los grados de todos los vértices de un grafo es dos veces su número de aristas.
c) Algoritmo para encontrar el bucle de Euler en un grafo de Euler
Se encuentra un ciclo cualquiera en el grafo G. Si el ciclo es G, él mismo es el bucle de Euler. Si no, entre las aristas restantes, se escoge otro ciclo que se pueda pegar por un vértice al primero y se dibujan ambos en forma de circunferencia. Si ambos ciclos son G, se recorre el grafo, siguiendo el dibujo de los ciclos pegados por el vértice en sentido del reloj o en sentido contrario, siendo este el bucle de Euler. Si no, se vuelve al paso donde se escoge otro ciclo entre las aristas restantes.
d) Teorema de las potencias de la matriz de adyacencias de un grafo
Si A es la matriz de adyacencias de un grafo G de n vértices, entonces la entrada (i,j) de la matriz Ak es el número de caminos de longitud k que hay en G (donde k varía entre 1 y n).