En materia de teorica, hemos visto los teoremas de Euler sobre las aristas, asi como el de Hamilton sobre los vértices. Ademas de el calculo de las componentes conexas. En practica, estamos trasteando el Magrada de los ***** jajjajaja xD
Teorica
Cálculo de las componentes conexas
Para el cálculo de las componentes conexas de un grafo nos encontramos con dos métodos.
- Con el primer método nos ayudaremos de las matrices de accesibilidad y de acceso del grafo.
- El segundo método tratará de realizar el producto de las matrices de acceso y de accesibilidad del grafo de manera que se estudiará como ver las componentes conexas en el resultado del producto nombrado.
Primer método:
Con la siguiente matriz de accesibilidad, para un grafo G dirigido, hallamos la matriz de acceso haciendo la traspuesta.
A partir del conjunto de vértices V={1, 2, 3, 4, 5, 6, 7} se elige uno de ellos y se realiza R(v)∩ Q(v) del que se obtendría los vértices a los que accede ’1′ y los que acceden a él: {1, 2, 4, 5}∩{1} = {1}. Dicho resultado es la primera componente conexa.
Después de hallar R(v)∩ Q(v) se resta al conjunto V el resultado de R(v)∩ Q(v) y obtendremos el conjunto de vértices V2.
V~R(v)∩ Q(v) = V2={2,3,4,5,6,7}
Con el conjunto obtenido elegimos un vértice de dicho conjunto y realizamos el mismo proceso hasta que:
Vn~R(v)∩ Q(v)=Ø
Segundo método:
Para la siguiente matriz de accesibilidad (R), se ha de hacer la matriz de acceso (Q) al igual que en el método anterior haciendo la traspuesta de la matriz de accesibilidad, y , seguidamente, hacer el producto de ambas RxQ.
Del resultado que obtengamos del producto RxQ tendremos que observar las filas de la matriz y fijarnos donde hay unos. Cada fila que esté compuesta por unos será una componente conexa, y los unos representan los vértices pertenecientes a esa componente. En el caso de que hubiera varias filas iguales no haría falta poner una componente conexa igual, ya que se trata de la misma información.
Euler: Caminos y Tours eulrianos (recorrido de aristas)
Conceptos:
- Tour: cadena cerrada que atraviesa cada arista del grafo G al menos una vez.
- Tour euleriano: cadena cerrada que atraviesa cada arista del grafo G exactamente una vez.
- Grafo euleriano: es aquel grafo G que contiene un tour euleriano.
- Camino euleriano: cadena simple que atraviesa cada arista de un grafo G exactamente una vez.
- Un grafo es euleriano si, y sólo si, no tiene vértices de grado impar.
- Un grafo contiene un camino euleriano si, y sólo si, tiene exactamente dos vértices de grado impar.
Para hallar si un grafo contiene un tour o un camino se ha de utilizar el algoritmo de Fleury.
Si el grafo es euleriano, a partir de un vértice cualquiera de G, construiremos una cadena simple de forma que no se repitan aristas y no se elijan aristas de corte (que dejen aislado a un vértice). Al finalizar este proceso, cuando hayamos agotado todas las aristas, habremos obtenido un tour euleriano.
Si el grafo contiene un camino comenzaremos con uno de los vértices de grado impar, siguiendo el mismo proceso descrito pero terminando la cadena con el otro vértice impar como vértice final.
Grafo con Tour euleriano:
Tour: e3 , e4 , e10, e9 , e7, e1 , e5 , 68 , e6 , e2.
Hamilton: Caminos y Ciclos hamiltonianos (recorrido de vértices)
Conceptos:
- Un camino hamiltoniano en un grafo G es un camino que atraviesa cada vértice del grafo exactamente una vez.
- Un ciclo hamiltoniano en un grafo G es un ciclo que atraviesa cada vértice del grafo exactamente una vez. Recordemos que un ciclo es una cadena simple cerrada con todos sus vértices internos distintos.
- Un grafo es hamiltoniano si contiene un ciclo hamiltoniano.
Aún no se ha determinado ningún tipo de algoritmo que pueda hallar si un grafo es hamiltoniano o no. Pero si que existen algunas condiciones establecidas para una gran variedad de grafos.
- Regla 1: si G no es conexo, no posee ciclos hamiltonianos.
- Regla 2: si G es un grafo con n vértices, entonces un camino hamiltoniano debe tener exactamente n-1 aristas, y un ciclo hamiltoniano n aristas.
- Regla 3: si v es una vértice del grafo, entonces un camino hamiltoniano debe tener al menos una arista incidente con v y como mucho dos.
- Regla 4: si G es hamiltoniano, entonces del grado de v debe ser mayor o igual que 2.
- Regla 5: si v tiene grado 2, entonces las dos aristas incidentes con v deben aparecer en cualquier ciclo hamiltoniano de G.
- Regla 6: si v tiene grado mayor que 2, en un ciclo hamiltoniano, una vez que ese vértice ya haya sido utilizado, la aristas no utilizadas incidentes con v se dejan de tener en cuenta.
- Regla 7: al construir un ciclo o camino hamiltoniano para un grafo G, no se puede dar el caso de obtener un ciclo para un subgrafo de G a menos que contenga todos los vértices de G.
Para un grafo G bipartido con partición {X,Y}:
- Si G tiene un ciclo hamiltoniano, entonces card(X)=card(Y).
- Si G tiene un camino hamiltoniano, entonces card(x) y card(Y) se diferencian como mucho en 1.
Teorica
- Grado: nos diŕa el grado del vértice que toquemos si nos encontramos en el modo gráfico o nos mostrará una gráfica con los grado de cada uno de los vértices si nos encontramos en el modo texto.
- Ver (aristas o arcos): para el modo texto, ya que no se ven ni aristas ni arcos, tenemos esta opción, que nos mostrará una pantalla donde pondrá las aristas (arcos) que van de un vértice a otro.
- Grafo (simple, cíclico, completo y conexo): tanto en modo texto como en modo gráfico podemos comprobar si un grafo es simple, cíclico, completo y conexo. En cualquiera de las opciones anteriores, nos indicará si lo es o no con una explicación.
- Grafo no dirigido asociado: esta opción, si estamos con un grafo dirigido nos creará un grafo con las mismas propiedades pero no dirigido, es decir, se cambian arcos por aristas.
——————————————
Hasta la semana que viene!!!!!! xD