Ver Ficha de aprendizaje del Tema 6
FICHA DE APRENDIZAJE DEL TEMA 6
1. ¿Qué significa que un vértice de un grafo alcance a otro vértice del grafo?
Un grafo es conexo si todo par de vértices está conectado, es decir, si existe un camino entre cualquier par de vértices distintos; si no es así, entonces el grafo puede “trocearse” y en cada “trozo” todos los vértices están conectados.
La CC a la que pertenece Vi estará formada por aquellos vértices que son alcanzables desde Vi, es decir, R(Vi) y que además alcanzan a Vi, es decir, Q(Vi). Es decir, la CC de Vi estará formada por R(Vi)nQ(Vi).
2. ¿Cuántas matrices Ri aparecen en la sucesión del algoritmo de Warshall para calcular la matriz de accesibilidad R de un grafo de 5 vértices?
Aparecen 5, ya que es una matriz 5x5, es decir, tiene cinco filas y cinco columnas. Después se hace un paso más para cambiar toda la fila en diagonal, por 1, en el caso que hubieran 0, (en caso contrario se deja como esta).
3. Escribe una condición necesaria para que un grafo sea conexo.
Un grafo es conexo si todo par de vértices está conectado, es decir, si existe un camino entre cualquier par de vértices distintos; si no es así, entonces el grafo puede “trocearse” y en cada “trozo” todos los vértices están conectados.
Como ya he comentado antes, un grafo es conexo si y sólo si el nº de componentes conexas es 1.
4. Representa gráfica y matemáticamente un grafo dirigido no simple que tenga un tour y un camino euleriano.
5. Si G es un grafo no dirigido con unos vértices de grado par y otros de grado impar ¿Cuándo podemos asegurar que G tiene un camino euleriano?
Grafos eulerianos GND: Teorema 1. Sea G un grafo no dirigido y conexo.
1º G es euleriano, (tiene tour-e) si y sólo si no tiene vértices de grado impar.
2º G contiene un camino euleriano no cerrado si y sólo si tiene exactamente 2 vértices de grado impar.
