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 de ser conexo.

7. - Grado de un vértice: Es el número de aristas adyacentes al vértice.

7.1. - Vértice aislado: Grado = 0

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) es subgrafo 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 un camino 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 regular de 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.

17. - Radio de G: 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), son isomorfos 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 cambiar las filas y entonces las columnas de las matrices de adyacencia y así igualaras.

21. - Camino de Hamilton: Con |V| " 3, es todo camino elemental que contiene a todos los vértices de G, grafo conexo.

22. - Ciclo de Hamilton: Con |V| " 3, es un ciclo que contiene todos los vértices de G, grafo conexo.(G nunca tendrá bucles).

20.1. - Grafo Hamiltoniano: Si posee ciclo de Hamilton.

20.2. -Theorema1: Si G es conexo, n"3y para todo vértice se verifica que gr(v)"n/2 entonces G es hamiltoniano.(no se puede reemplazar el entero n/2 por su mayor entero más cercano).

20.3. - Theorema2: Un grafo hamiltoniano no tiene vértices de corte.

20.4. - Theorema3: G con |v|"2 y se verifica gr(v)+gr(w) "n-1 para todo v, w de V, entonces G posee un camino de Hamilton.

Corolario: G sin bucles con n"2, G tiene un camino de Hamilton si gr(v)"(n-1)/2, para todo v de V.

20.5. - Theorema4: G tiene un ciclo de hamilton si gr(u)+gr(v)"n siendo v y no adyacentes.

Corolario1: G es un grafo (no digrafo) y es hamiltoniano si gr(v) "n/2 para todo v de V.

Corolario2: G (no digrafo) con |v|= n"3 es hamiltoniano si |E|"(nºcombinatorio n-1 sobre 2) +2.

23. - Regular:

21.1. - Digrafo: Todos los grados de entrada de los vértices tienen que ser iguales.

21.2. - Grafo: Todos los grados tienen que ser iguales.

24. - Centro de G: El conjunto de todos los vértices tal que e(v)=r(v).

24.1. - Vértice central: Cada uno de los vértices que forman el centro.

25. - Vértice de corte o articulación: Es un vértice que al suprimirlo junto con todos sus arcos, se genera un subgrafo de G que tiene más componentes que G.

26. - Arco de corte o puente: Cualquier lado de G que al suprimirlo produzca un subgrafo de G con más componentes que G.

Árboles

Son un tipo especial de grafo.