INTRODUCCION A LOS GRAFOS
Un grafo es un par ordenado , donde:
- es un conjunto de vértices o nodos, y
- es un conjunto de aristas o arcos, que relacionan estos nodos.
Normalmente suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.
Se llama orden del grafo a su número de vértices, .
El grado de un vértice o nodo es igual al número de arcos que lo tienen como extremo.
Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
Dos o más aristas son paralelas si relacionan el mismo par de vértices.
Grafo dirigido
Un grafo dirigido o digrafo es un grafo donde:
- es un conjunto de pares ordenados de elementos de .
Dada una arista , es su nodo inicial y su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
Grafo no dirigido
Un grafo no dirigido o grafo propiamente dicho es un grafo donde:
- es un conjunto de pares no ordenados de elementos de .
Un par no ordenado es un conjunto de la forma , de manera que . Para los grafos, estos conjuntos pertenecen al conjunto potencia de , denotado , y son de cardinalidad 2.
ARISTA
Es un arco de un grafo no dirigido
VERTICES ADYACENTE
vértices unidas por un arco
FACTOR DE PESO
valor que se puede asociar con un arco
depende de lo que el grafo represente
si los arcos de un grafo tienen f.p.
grafo valorado
un camino por un grafo g, desde Vo a Vn
LONGITUD
el numero de arcos que lo forman
CAMINO SIMPLE
todos los nodos que lo forman son distintos
CICLO
camino simple cerrado de long. >=2
donde Vo = Vn
camino A y A
P = {A,E,B,F,A,}
longitud 4 - 4ciclos
MATRIZ DE ADYACENCIA
dado un grafo g = (V,A)
sean los vertices V = {(Vo,V)....,Vn}
se pueden representar por ordinales 0,1...n
como representar los arcos
estos son enlaces entre vertices
puede usarse una matriz
{i, si hay arcos (Vi,Vj)}
G ij
{o, si no hay arco (Vi,Vj)}
Comentarios