Juan Jesus Rosales Sandoval
GRAFOS
Los grafos son estructuras discretas que constan de vértices y aristas que conectan entre si esos vértices.
Por lo tanto un grafo G costa de dos partes:
1) Un conjunto V = V (G) cuyos elementos se denominan vértices, puntos o nodos de G.
2) Un conjunto E = E(G) de pares de vértices distintos denominados aristas de G.
Hay dos tipos básicos de grafos:
Grafo dirigido
Sea V un conjunto finito no vacío, y sea la relación binaria E ⊆ V xV . El par ordenado (V, E) es un grafo
dirigido sobre V, o dígrafo, donde V es el conjunto de vértices o nodos y E es su conjunto de aristas.
Escribimos G = (V, E) para denotar tal dígrafo.
En la Figura 1 se puede ver como se representan los grafos dirigidos o dígrafos, con vértices V =
{A, B, C} y aristas E = {(B, A),(A, C),(C, A),(C, B)}.
Grafo no dirigido
Cuando no importa la dirección de las aristas, la estructura G = (V, E), donde E es ahora un conjunto de
pares no ordenados sobre V, es decir el conjunto de aristas representa una relación simétrica binaria, donde
si Vj y Vk son vértices cualesquiera del conjunto de vértices V de un grafo, (Vj , Vk) ∈ E −→ (Vk, Vj ) ∈ E.
Decimos que tenemos un grafo no dirigido.
En la Figura 2 se puede ver como se representan los grafos no dirigidos, con vértices V = {A, B, C, D}
y aristas E = {(A, B),(B, C),(C, D),(D, A)}.
CAMINOS
Es un grafo desde Vo a Vn
camino entre 4 y 7
p={4,5,6,7}
longitud = 3 , por que tiene 3 aristas
Comentarios
Publicar un comentario