Partes del grafo
grafo (G) es un diagrama que consta de un conjunto de vértices (V) y an conjunto de lados (L).
Bajo estas condiciones una taza de café y una dona son topológicamente equi valentes ya que deformando y estiran do cualquiera de ellas se obtiene la otra como resultado de la transformación.
El nacimiento de la topología se suele ubicar en el año 1735, cuando Euler re solvió el problema de los puentes de Kónigsberg, solución que no sólo exhi be un enfoque totalmente topológico, sino que además aporta el primer inva riante de la topología algebraica.
Hacia finales del siglo XVill el punto de partida del desarrollo sistemático de la topología fue la definición rigurosa de conceptos fundamentales del análisis como función, continuidad, diferenciabi- lidad, así como el estudio de las nuevas geometrías no euclideanas y de objetos geométricos como la banda de Móbius (1858) que se muestra a continuación
(continuación)
la cual fue descubierta en forma inde pendiente por los matemáticos alema nes August Ferdinand Móbius y Johann Benedict Listing en 1858. Como se puede ver, esta banda se caracteriza por ser una superficie con un solo lado y un solo contorno ade más de ser un objeto no orientable.
Considérese el siguiente grafo:
Vértices (nodos)
Se indican por medio de un pequeño círculo y se les asigna un núme:: letra. En el grafo anterior los vértices son V = {a, b, c, d}.
• Lados (ramas o aristas) ^
Son las líneas que unen un vértice con otro y se les asigna una letra, número o una combinación de ambos. En el grafo anterior los lados L = {1, 2, 3, 4, 5, 6).
• Lados paralelos
Son aquellas aristas que tienen relación con un mismo par de vértices. I el grafo anterior los lados paralelos son: P = {2, 3}.
• Lazo
Es aquella arista que sale de un vértice y regresa al mismo vértice. En grafo anterior se tiene el lazo: A = {6}.
• Valencia de un vértice
Es el número de lados que salen o entran a un vértice. En el grafo ante" las valencias de los vértices son:
Valencia (a) = 2
Valencia (b) = 4
Valencia (c) = 2 Valencia (d) = 3
Hay que observar cómo en el caso del vértice d el lazo sólo se consid una vez, entrada o salida pero no ambos.
7.3 Tipos de grafos
• Grafos simples
Son aquellos grafos que ño tienen lazos ni lados paralelos.
