Teoría de Gráficas

Teoría de Gráficas

1. Camino/ciclo hamiltoniano.- Dado un grafo G, un circuito hamiltoniano para G es un circuito simple que incluye todos los vértices de G. Es decir, un circuito hamiltoniano para G es una sucesión de vértices adyacentes y aristas distintas en las que aparece exactamente una vez cada vértice de G, excepto el primero y el último, que son los mismos.

2. Camino/ciclo euleriano.- Sea G un grafo. Un circuito de Euler para G es un circuito que contiene cada vértice y cada arista de G. Es decir, un circuito de Euler para G es una sucesión de vértices adyacentes y aristas en G que tiene al menos una arista, que comienza y termina en el mismo vértice, utiliza cada vértice de G por lo menos una vez y cada arista de G exactamente una vez.

3. Matriz de incidencia.- Sea G =(V, E) un grafo no dirigido. Supongamos que v1, v2,, … , vn son los vértices y e1, e2, …, en las aristas de G. Entonces, la matriz de incidencia con respecto a este ordenamiento de V y de E es la matriz M =[mij] de n X m dada por

4. Gráfica (grafo).- Un grafo G puede representarse geométricamente asignando a cada vértice un punto en el plano, representando cada arista como una línea uniendo sus extremos. La figura muestra un grafo G con conjunto de vértices V (G) = {1, 2, 3, 4} y conjunto de aristas E(G) = {e1 , e2, e3 , e4 }.

5. Vértice (nodo).- Los puntos del grafo se llaman vértices o nodos y representan los elemen- tos del conjunto, se denominan el conjunto de puntos: V(G).

6. Bucle.- Cuando una arista conecta un vértice consigo mismo, se llama un bucle.

7. Arista (arco).- Las líneas que conectas un par de vertices: E(G).

8. Vértices adyacentes.- dos vértices que se conectan por una arista se denominan adyacentes; y un vértice que es un punto final de un bucle se dice que es adyacente a sí mismo.

9. Matriz de adyacencia.- Sea G un grafo dirigido con vértices ordenados v1, v2, ... , vn. La matriz de adyecencia de G es la matriz n X n A = (aij) sobre el conjunto de enteros no negativos tales que aij = al número de flechas de vi a vj para toda i, j = 1,2, ..., n.

10. Grado de un vértice.-Sea G un grafo y u un vértice de G. El grado de v, que se denota por deg(v), es igual al número de aristas que inciden en u, con una arista que es un bucle contado dos veces; El grado total de G es la suma de los grados de todos los vértices de G.

11. Grafo simple.- Un grafo simple es un grafo que no tiene ningún bucle o aristas paralelas. En un grafo simple, una arista con puntos extremos u y w se denota por (v, w).

12. Multigrafo.- Un multigrafo G = (V, E) consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en { {u,v} | u, v ∈ V, u ≠ v }. Se dice que las aristas e1 y e2 son aristas múltiples o paralelas si f(e1) = f(e2)

13. Digrafo (digráfica).- Una digráfica G consiste en un conjunto V de vértices y un conjunto E de aristas (o arcos) tales que cada arista e ∈ E está asociada con un par ordenado de vértices. Si hay una arista única e asociada con el par ordenado (v, w) de vértices se escribe e=(v,w), que denota una arista de v a w.

14. Camino.- Un camino de v a w es una sucesión finita alternada de vértices adyacentes y aristas de G. Por tanto un camino tiene la forma v0 e1 v1 e2 ... vn-1 en vn donde las v representant vértices, las e representant aristas, v0 = v, vn = w y para toda i = 1,2, ... n, vi-1 y vi son los puntos extremos de ei. El cmaino trivial de v a v consiste del único vértice v.

15. Ciclo (circuito).- Es un camino cerrado que contiene al menos una arista y no contiene una arista repetida.

16. Árbol.- Un grafo se llama árbol si y sólo si, está libre de circuitos y es conexo. Un árbol trivial es un grafo que consta de un único vértice.

17. Árbol de expansión.- Un árbol expandido para un grafo G es un subgrafo de G que contiene cada vértice de G y es un árbol.

18. Relación binaria.- Sea A un conjunto no vacío. Una relación binaria en A , es un subconjunto R de A × A: Si( a, b ) ∈ R, se acostumbra escribir aRb , y se dice que “ a está relacionado con b ”.

19. Digráfica de una relación.- Una manera informativa de visualizar una relación en un conjunto es dibujar su digráfica. Para dibujar la digráfica de una relación en un conjunto X, primero dibujamos puntos o vértices para representar los elementos de X.

20. Matriz de una relación.- Sea A = {a1, ..., an } un conjunto finito, y sea R una relación binaria en A . Podemos describir R por medio de la matriz:

    • donde:
      • Se acostumbra escribir MR = (rij) y se le llama la matriz de la relación R .

21. Propiedades de una relación

    • R es reflexiva si y sólo si, para toda x ∈ A, x R x.
      • R es simétrica si y sólo si, para toda x, y ∈ A, si x R y entonces y R x.
        • R es transitiva si y sólo si, para toda x, y, z ∈ A, si x R y y y R z entonces x R z.
          • Sea R una relación sobre un conjunto A. R es antisimétrica si y sólo si, para todos a y b en A, si a R b y b R a entonces a D b.

22. Cerradura transitiva de una relación.- Sea R una relación binaria en un conjunto finito A, entonces R∞ es la cerradura transitiva de R.

23. Relación de equivalencia.- Sea A un conjunto y R una relación sobre A. R es una relación de equivalencia si y sólo si, R es reflexiva, simétrica y transitiva.

24. Cerradura transitiva de una relación.- Sea R una relación binaria en un conjunto finito A, entonces R∞ es la cerradura transitiva de R.

Imágenes y archivos del mapa