8.3 Teoria de graficas

Grafos: Modelos matematicos que sirvan para representar las relaciones entre objetos de un conjunto. Es un conjunto de vertices, cosas o nodos conectados a traves de aristas.

REPRESENTACION G(V,E)
V: Vertices
E: Aristas

Tipos de grafos

Simples: lineas entre puntos, pero solo un camino de un punto a otro
Multigrafo: representa diferentes caminos para llegar al mismo punto
Pseudografo: perifericos o caminos que salen de un punto A y regresan al mismo punto A
Grafo ponderado: nodos unidos por lineas pero con unidades metricas que nos representan una unidad o recurso para optimizar las rutas
Grafo dirigido: caminos de una sola via de un punto a punto a otro, sin retorno.
Multigrafo dirigido: caminos de una sola ruta pero con varias rutas para llegar al mismo punto.

Grado un vertice
Aristas -> Caminos
Vertices -> Nodos
El grado de un vertice(nodo) lo determinan el numero de aristas incidentes en un vertice V. Es decir el grado es igual al numero de vertices adyacentes.

Existe una propiedad que establece: La sumatoria de todos los grados de los vertices sera igual al doble de aristas del grafo.

NOTA:

Si la arista es un bucle en un vertice, contribuye con dos unidades al valor del grado. Esto porque cada conexion de la arista del bulce cuenta como su propio vertice de adyacencia, un vertice con un bucle se ve a si mismo como un nodo adyacente a ambos vertices finales de la arista.
Los vertices de grado creo se les denomina vertice aislado.

Teorema
Un grafo conexo G, es euleriano (ciclo euleriano) si, y solo si, todos los vertices son de grado par.

Un grafo conexo G contiene un recorrido euleriano si, y solo si , G tiene exactamente dos vertices de grado impar. Se inicia en uno de los vertices de grado impar y se finaliza el recorrido en el otro.

Ciclo de euler: Es un camino que pasa por cada arista una y solo una vez. Es un camino cerrado que recorre cada arista exactamente una vez. Inicia y finaliza en el mismo vertice.

Camino de Euler: Es un camino que pasa por cada arista una sola vez pero puede pasar por un mismo vertice varias veces.

Camino hamiltoniano: Es un camino de un grafo, una sucesion de aristas adyacentes, que visita todos los vertices del grafo una sola vez.

Caminos: Es una sucesion de vertices y conexiones donde no se puede repetir ningun vertice ni conexion.
Cadena: Es una sucecion de vertices y conexiones entre si, con las cuales se puede recorrer el grafo.
Ciclos: Es un camino donde lo unico que se repite es el vertice final.
Cadena cerrada: Se inicia y finaliza en el mismo vertice pero se puede repertir los vertices en el recorrido.
Conexo: Es donde se tienen todos los vertices conectados entre si.
No conexo: Cuando no podemos conectarnos con todos los grafos.

CONDICIONES PARA SABER SI HAY CAMINO HAMILTONIANO

Grado(u) + Grado(v) >= n-1, donde n es el numero de vertices y u y v son vertices.
La condicion anteorior no es necesaria ni suficiente para determinar si hay un camino hamiltoniano.
Cuando uno de los vertices de un grafo es de grado 1 no puede existir CICLO HAMILTONIANO. Si hay camino hamiltoniano pero no hay ciclo NO ES UN GRAFO HAMILTONIANO.

Matriz de adyacencia

Es otra manera de representar los grafos. Es muy util cuando el grafo se ha convertido muy complejo. Se ubican todos los vertices como titulos de columnas y filas. Se analiza nodo por nodo y se ubica uno en los vertices adyacentes al vertice en analisis.

Matriz de incidencia

Es una matriz binaria es decir solo puede tener 1 y 0. Las columnas son aristas y las filas son los vertices.

NOTA:

Grafo dirigido = matriz asimétrica
Grafo no dirigido = matriz simétrica (La primer fila y conlumna tienen los mismo elementos en el mismo orden)

Backlinks: Inteligencia Artificial:8. Matematicas discretas