Grafos

Resumen Grafos 1. − Vértices adyacentes: Dos vértices unidos por un arco. 2. − Bucle: Arco que sale de un vértice y entra en el mismo. 3. − Arcos paralelos: Son aquellos que unen los mismos vértices. 4. − Multigrafo: Es aquel grafo o digrafo que posee arcos paralelos. 5. − Etiquetado: Grafo cuyos vértices tienen valores asociados. 6. − Camino: Secuencia ordenada de vértices y arcos. 6.1. −Longitud del camino: Número de arcos que posee. (N) 6.2. − Camino trivial: N=0 6.3. − Camino cerrado: Cuyo inicio es igual que el final 6.4. − Camino abierto: Lo contrario. 6.5. − Camino simple: Sin arcos repetidos. 6.6. − Camino elemental: Sin vértices repetidos. Punto aislado: Es un camino elemental y simple de N=0 6.7. − Circuito: Camino simple cerrado. Al menos un arco, si es así: bucle. 6.8. −Ciclo: Camino elemental cerrado: n"3 Todo ciclo es un circuito. 6.9. − No conexo: Tiene dos componentes, al menos; no hay un camino simple entre cualquier vértice. Número de componentes del grafo K(G) 6.10. − Distancia: Es el mínimo camino elemental entre dos vértices. 6.11. − Excentricidad de v: e(v): Es el mayor de los caminos elementales desde v hasta cualquier otro vértice del grafo, éste ha deser conexo. 7. − Grado de un vértice: Es el número de aristas adyacentes al vértice. 7.1. − Vértice aislado: Grado = 0 1

7.2. − Bucle: Grado = 2 7.3. − Grado de entrada(sólo digrafos): Nº de aristas que entran en v Gr − (v) Fuente: Cuando Gr − (v) = 0 7.4. − Grado de salida (sólo digrafos): Nº de aristas que entran en v Gr + (v) Sumidero: Cuando Gr + (v) = 0 8. − Subgrafo de G: G1= (V1,E1) essubgrafo de G= (V,E) si V1" V y E1" E. 8.1. − Subgrafo Maximal: Cuando V1= V y E1 " E. 8.2. − Subgrafo de G inducido por U: Si G1 =(U,E1) y U " V y E1" E entonces G1 es un subgrafo de G inducido por U. E1 tiene que corresponder con E. 8.3. − Subgrafo de G inducido por G− {v}: Todo igual quitando ese vértice v y las aristas adyacentes a ese vértice. 9. − Grafo Unión: Si G1=(V1,E1) y G2=(V2,E2)entonces G1 " G2 = (V1 " V2, E1 " E2) 10. − Matriz de adyacencia: De G respecto de V={v1,v2,v3,...,vn} es booleana. Un elemento de A será 1 si los vértices son adyacentes. 10.1. − El número de caminos distintos de longitud r de vi a vj es el valor del elemento de A aij" Ar 11. − Matriz de incidencia: Es booleana; aij=1 si ej es incidente con vi 12. − Camino simple de Euler: En un grafo conexo es uncamino simple que pasa por todos los arcos. 12.1. − Si tiene sólo 2 vértices de grado impar entonces tiene un camino de Euler que empieza por un vértice de ellos y acaba en el otro. 13. − Circuito de Euler: Circuito de un grafo conexo que pasas por todos los lados. 13.1. − Si todos los vértices son de grado par el grafo lo tiene. 13.2. − Grafo Euleriano: Si posee circuito de Euler. 14. − Grafo regularde Grado K: Un grafo cuyos vértices son de grado K 15. − Grafo completo (no digrafo): G lo es si para los n vértice cada uno es adyacente con los n−1 restantes. Tiene vértices. 16. − Bipartido: Si V=V1"V2 y {0}=V1"V2 y G es de la forma {a,b} con a"V1 y b"V2. 16.1. − Bipartido completo: Si cada a"V1 es adyacente con cada b"V2. Km, n 16.2. − Tampoco pueden encontrarse bucles. 2

17. − Radio deG: r(G): Es el valor mínimo de las excentricidades de todos los vértices. 18. − Diámetro de G: di (G): Es el valor máximo de las excentricidades de los vértices. 19. − Complemento de G (G´): Es un grafo con todos los vértices de G y todos los lados que no tenga G. 17.1. − Para que G tenga complemento, no debe tener bucles. 20. − Grafos isomorfos: Dos grafos simples, G1=(V1, E1) y G2=(V2, E2), sonisomorfos si existe una aplicación f: V1!V2 que sea biyectiva y " a, b " V1 {a, b} " E1 ! {f(a), f(b)} " E2. 18.1. − Condiciones en la practica: G1 y G2 tienen que tener el mismo número de vértices y de arcos. Si u es adyacente con v en G1, entonces f(u) lo ha de ser con f(v). Si gr(u)=K entonces gr(f(u))=K. K(G1)=K(G2) Los dos tienen que tener los ciclos de la misma longitud. Se ha de poder...