1. ¿Qué significa que un vértice de un grafo alcance a otro vértice del grafo ?
Significa que un vértice es accesible a otro, esto se puede representar en la matriz de accesibilidad, en la que si vemos que un cierto elemento vale 1, pongase por ejemplo el elemento 1-1, diremos que el vértice 1, alcanza o es accesible al vértice 1, esto pasa siempre, un vértice se alcanza a si mismo, en otros casos habría que ver si existe un camino entre un vértice y otro para poner asi el 1 o el 0 al elemento correspondiente.
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?
Al tener 5 vertices el algoritmo de Warshall ira desde R0 hasta Rn donde n es el numero de vértices del grafo, es decir, en este caso, hasta R5, donde R0 es la matriz de adyacencia modificada de forma que todos los elementos que no sean 0 deben ser 1, y R1 y sucesivos son matrices calculadas a partir de unos criterios que aparecen en la imagen a continuación.
3. Escribe una condición necesaria para que un grafo sea conexo.
Un grafo es conexo siempre y cuando las componentes conexas de ese grafo = 1.Eso quiere decir que ese grafo no se puede dividir en subgrafos por que de todos los vértices de ese grafo hay una cadena que los conecta a todos con todos. De cualquier vértice mediante una cadena puedes llegar a otro, todo par de vértices está conectado.
4. Representa grafica y matemáticamente un grafo dirigido no simple que tenga un tour y un camino euleriano .
El grafo anterior tiene un tour ya que tiene una cadena cerrada que atraviesa cada arco al menos una vez y tiene un camino euleriano porque tiene una cadena simple que atraviesa cada arista exactamente una vez.
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?
Según el teorema, podemos asegurar que G tiene un camino euleriano si y solo si el numero de vértices con grado impar es 2 y G es un grafo conexo