Grafo conexo java

1.Explica con claridad los siguientes pares de conceptos, dejando claro sihay alguna relación entreellos:

a)Grafo Recorrible y grafo deEuler.

b)Ciclo y bucle de ungrafo.

c)Árbol y subgrafo economía de ungrafo.

d)Grafo conexo y componente conexa de  ungrafo.

a)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 deEuler.

b)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 alrevés.

c)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 hayan si elimino unaarista.

d)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 Contario no es cierto (se  debería dar unejemplo)

2.Enuncia con Precisión y detalle los siguientesresultados:

a)Teorema de caracterización de grafos deEuler.

b)Teorema de las aristas y los grados de los Vértices de ungrafo.

c)Algoritmo para encontrar el bucle de Euler en un grafo deEuler.

d)Teorema de las potencias de la matriz de Adyacencias de ungrafo.

a)Todo Grafo G es de Euler si y solo si G es conexo y todo vértice es de gradopar.

b)La suma de los grados de todos Los vértices de un grafo es dos veces su número dearistas.

c)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 éste el bucle de Euler. Si no, se vuelve al paso donde se escoge otro ciclo entre las aristasrestantes.

d)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 (k varía entre 1 y n).