discretas

Grafo:Coleccion de elemntos llamados nodos o verticves que pueden estar solos o conectados con otros nodos, estan conectados por lineas que se llaman lados o aristas y si no esta conectado es unnodo: aislado
Lazo: que el nodo este conectado con si mismo
Nodos paralelos: Dos cominos que conectan los mismos nodos
Grafos simples: no tiene ni nodos ni lados paralelos
Grafo conexo. Enmatemáticas y ciencias de la computación es aquel grafo que entre cualquier par de sus vértices existe un Camino (Grafo) que los une.
Grafo bipartito: cuyos vértices se pueden separar en dos conjuntos disjuntosde manera que las aristas sólo pueden conectar vértices de un conjunto con vértices del otro.
Grafo bipartito (o bipartido) completo es aquel grafo bipartito en el que todos los vértices de lapartición están conectados a todos los vértices de la partición y viceversa.
Ciclo de Euler: Recorre todas las aristas del grafo sin repetir ninguna.
Teorema: Sea G un grafo (finito y conexo).
(a) lasuma de las valencias de todos sus vertices es par. Es decir, hay un “número par de vértices impares”.
(b) Si el número de vértices impares es mayor que dos, el grafo no se puede recorrer [sin pasardos veces por ninguna arista].
(c) Si el número de vértices impares es cero, el grafo se puede recorrer. Podemos además elegir por qué vértice empezar, y el camino siempre será cerrado (termina dondeempezó).
(d) Si el número de vértices impares es dos, el grafo se puede recorrer, pero el camino ha de empezar en uno de los dos vértices impares y terminar en el otro.
Matriz para recorrer elgrafo sin repetir ningúna arista



Matriz de Euler: A,B,C,D,B,E,D,F,E,C,A
Se recorren todas sus aristas sin repetirlas
Ciclo de Hamilton: W.R. Hamilton (1805-1865) inventó (y patentó) un juego enel que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro....