Arboles

Alejandra Carrillo Moreno 211

Un GRAFO O GRAFO NO ORIENTADO es una terna G = {V, A,j } conV ¹ f
donde:
V = {v1, v2, …, vn}: conjunto finito de vértices o nodos.
A = {a1, a2, …, an}: conjuntofinito de aristas o lados y
j :A à X(V) función de incidencia, siendo X(V) ={X: X Í V Ù X = 1 ó 2 }
Notación :Si j (a) = {u ,v}se dice que:
· u y v son los extremos de a
· u y v son vérticesadyacentes
· la arista a es incidente en los vértices u y v.

DEFINICIÓN 2:
Un DIGRAFO O GRAFO ORIENTADO es una terna por la terna D = (V, A,j ) con V ¹ f
donde:
V = {v1, v2, …, vn}: conjunto devértices o nodos.
A = {a1, a2, …, an}: conjunto de aristas o arcos
j :A à V × V función de incidencia.
Notación: Si j (a) = (v ,w) se dice que
· los vértices v y w son adyacentes
· a incidepositivamente en w y negativamente en v.
· v es extremo inicial de la arista a, w es extremo final de a

DEFINICIONES RELATIVAS A GRAFOS (DIGRAFOS)
ARISTAS ADYACENTES: Aristas que tienen un solo extremoen común
ARISTAS PARALELAS O MÚLTIPLES:
Un grafo (digrafo) posee aristas paralelas sii j no es inyectiva.
Es decir, dado a1 Î A y a2 Î A, a1 y a2 son aristas paralelas sii j (a1) = j (a2).
LAZO OBUCLE: a Î A: lazo siij (a) = {v} (En grafos)
a Î A: lazo siij (a) = (v ,v) (En digrafos)
GRAFO (DIGRAFO) SIMPLE: Grafo (digrafo) que carece de aristas paralelas y lazos.
GRAFO COMPLETO: es elgrafo simple con mayor cantidad de aristas. Se indica con
Kn si tiene n vértices

GRADO DE UN VÉRTICE O VALENCIA (EN GRAFOS)
GRADO DE UN VÉRTICE : g(v) es la cantidad de aristas incidentes en él,contando
doble en el caso de lazo.
Obs: Si g(v) = 0 se dice que v es vértice aislado.
Propiedades:
1. En G = {V, A,j } . A 2 ) ( å
Î
=
v V
g v
Es decir: la suma de los grados de los vértices deun grafo es igual a al doble de la
cantidad de aristas.
2. La cantidad de vértices de grado impar de un grafo G= {V ,A,j } , es un
número par .

GRADO DE UN VÉRTICE O VALENCIA (EN DIGRAFOS)...