5.1 Elementos características y componentes de los grafos

5.1 Elementos y Características de los Grafos

A partir de esta figura se definen los siguientes elementos:

Vértices (nodos) 

Se indican por medio de un pequeño círculo y se les asigna un número o 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, un numero o una combinación de ambos. En el grafo anterior los lados son:

L= {1, 2, 3, 4, 5, 6}.

Lados paralelos

Son aquellas aristas que tienen relación con un mismo par de vértices. En 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 el 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 anterior las valencias de los vértices son:

Valencia (a)=2

Valencia (b)=4

Valencia (c)=2

Valencia (d)=3

Aristas:

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a, b} es una arista, a los vértices a y b se les llama sus extremos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

• Cruce: Son dos aristas que cruzan en un punto.

Vértices:

Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

• Vértice Aislado: Es un vértice de grado cero.

• Vértice Terminal: Es un vértice de grado 1.

Matematicas Discretas. (s.f.). Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/6-1-elementos-y-caracteristicas-de-los-grafos

Matematicas Discretas. (s.f.). Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/6-1-1-componentes-de-un-grafo