5.1 Elementos, características y componentes de los grafos

5.1 Elementos, características y componentes de los grafos

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. "La notación G = (V, A) se utiliza comúnmente para identificar un grafo. 

 Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. 

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

*Vértices Adyacentes: si tenemos un par de vértices de un grafo (U,V) y si tenemos una 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.

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.

5.1.1 Tipos de grafos

Grafo simple

Un grafo simple G = (V, A) costa de un conjunto no vacío de vértices V y de un conjunto A de pares no ordenados de elementos distintos de V, a estos pares se les llama aristas. En otras palabras, un grafo simple es un grafo en los que existe a lo más una arista que une dos vértices distintos.

Multígrafos

Un multígrafo G = (V, A) consta de un conjunto V de vértices, un conjunto A de aristas y una función f de A hacia {{u, v} | u, v ꞓ V, u ≠ v}. Se dice que las aristas a1 y a2 son aristas múltiples o paralelas si f (a1) = f (a2).

Pseudografos

Un pseudografo G = (V, A) consta de un conjunto V de vértices, un conjunto A de aristas y una función f de A hacia {{u, v} | u, v ꞓ V}. Una arista a es un bucle o lazo, si f(a) = {u; u} = {u} para algún u ꞓ V.

Grafo dirigido

Un grafo dirigido G, también llamado digrafo, es lo mismo que un multigrafo, solo que cada arista e de G tiene una dirección asignada o, en otras palabras, cada arista e está identificada por un par ordenado (u, v) de nodos G en vez del par desordenado [u. v].

Multigrafo dirigido

Un multigrafo dirigido G = (V, A) consta de un conjunto V de vértices, un conjunto A de aristas y una función f de A hacia {〈u, v 〉 | u, v ꞓ V}. Se dice que las aristas a1 y a2 son aristas múltiples o paralelas si f (a1) = f (a2).

Grafo completo

Un grafo completo es un grafo simple que tiene una arista entre cada par de vértices distintos. Es decir es aquel en el que cada par de sus vértices está interconectado entre sí.

Fuentes:

*Enrique Chávez (s.f), Elementos y Características de Los Grafos, recuperado de: https://es.scribd.com/document/310274082/Elementos-y-Caracteristicas-de-Los-Grafos

*Grafos (s.f), de Wikimedia, recuperado de: https://upload.wikimedia.org/wikipedia/.../Introducción_a_la_Teoría_de_Grafos.pdf