5 Teoría de Grafos

5.1 Elementos, Características y componentes de los grafos

Una gráfica G (V, E) consiste en un conjunto no vació V llamado conjunto de vértices (nodos, puntos) y el conjunto E de pares ordenados o no ordenados de elementos de V denominado el conjunto de aristas, tales que hay un mapeo del conjunto E al conjunto de pares ordenados o no ordenados de elementos de V.

Si en la gráfica G = (V ,E) cada arista e ∈  E se asocia  con un par ordenados de vértices, entonces G recibe el nombre de gráfica dirigida o diagráfica, si cada arista se asocian un par no ordenados de vértices, entonces G, se llama gráfica no dirigida.

Una gráfica ( o gráfica no dirigida) G consta de un conjunto V de vértices (o nodos) y un conjunto E de aristas (arcos o lados) tales que cada arista e ∈ E queda asociada a un par no ordenado de vértices. Si existe una única arista e asociada con los vértices u y w escribimos e = (v, w) o e = (w, v). En este contexto (v, w) denota un arista entre v y w  en una gráfica no dirigida y no un par ordenado.

Una gráfica dirigida (o diagrafica) G consta de un conjunto V de vértices (o nodos) y un conjunto E de aristas (Arcos o lados) tales que cada arista e ∈ E se asocia con un  par ordenado de vértices 

e = (v, w)

5.1.1 Tipos de Grafos 

La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos. Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas).  Tipos de Grafos Grafo simple. o simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo. Multigrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido. Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad. Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices. Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Partes de un grafo.

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

• Nodos. Se indican por medio de un pequeño circulo y se le asigna un numero o una letra.
• Aristas. Son las lineas que unen un nodo con otro y se les asigna una letra un numero o una combinación de ambos.
• Aristas paralelas. Son las aristas que tienen relación con un mismo par de nodos.
• Lazo. Es aquella arista que sale de un nodo y regresa al mismo nodo.
• Valencia de un nodo. Es el numero de aristas que salen o entran a un nodo.

Referencias

Libros. (20 de agosto de 2016). Obtenido de http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro5/42_tipos_de_grafos.html

Rodriguez, C. (18 de junio de 2008). BRAINLY. Obtenido de https://brainly.lat/tarea/271716