Elementos, características y componentes de los grafos

¿Qué es…?

Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es, pues, un subconjunto {a, b}, con a, b ∈ V, a = b.

Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).

•          Vértices (nodos)

Se indican por medio de un pequeño círculo y se les asigna un número o letra.

•          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.

•          Lados paralelos

Son aquellas aristas que tienen relación con un mismo par de vértices.

•          Lazo

Es aquella arista que sale de un vértice y regresa al mismo vértice

•          Valencia de un vértice

Es el número de lados que salen o entran a un vértice.

Tipo de Grafos

•          Grafos simples

Son aquellos grafos que no tienen lazos ni lados paralelos.

•          Grafo completo de n vértices (Kn)

Es el grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo.

•          Complemento de un grafo (G ')

Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.

•          Grafo bipartido

Es el grafo que está compuesto por dos conjuntos de vértices, A = {a1, a2, a3..., an} y B = {b1, b2,…., bm} en donde los elementos del conjunto A se relacionan con los del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una.

•          Grafo bipartido completo (Kn> m)

Es el grafo que está compuesto por dos conjuntos de vértices, uno de ellos

A = {a1, a2, a3,..., an} y otro B = {b1, b2,..., bm], y en el que cada vértice de A esta unido con todos los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se índice como Knm.

Referencias:

Murillo, J. A. (n.d.). Matemáticas para la computación. In J. A. Murillo, Matemáticas para la computación (pp. 287-292). México: Alfaomega.