Terminología de la teoría de grafos

Question	Answer
INTRODUCCIÓN	Leonhard Euler fue el más grande matemático, filósofo y físico suizo. Nació el 15 de abril de 1707 en Basilea (Suiza).Siendo un adolescente ingresó a la Universidad de Basilea, donde a los 17 años de edad, se graduó Doctor, provocando grandes aplausos con un discurso probatorio
Concepto de grafo	sea V el conjunto no vacío de vértices o nodos y E el conjunto de lados o aristas (pares de vértices); se dice que G es un grafo, si G= (V, E) es una estructura de datos compuesta por esos dos conjuntos V y E que forman un conjunto de pares ordenados o desordenados de vértices o nodos. Los pares de vértices van entre paréntesis y los pares desordenados, pondrán entre llaves.
Grafo dirigido	Un grafico dirigido G, también llamado “dígrafo o digrafo”, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices. Un grafico dirigido G, también llamado “dígrafo o digrafo”, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices
Grafo no dirigido	Un grafo no dirigido (vea figura 10.1b) consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices. Si existe una única lista e asociada con los vértices v y w, escribimos e = {v,w} ó e = {w,v}. en este contexto, {v,w} denota una arista entre v y w en un grafo no dirigido y no un par ordenado. En conclusión un grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado (vea figura 10.1d).
Grafo dirigido con peso	es aquel grafo dirigido en el que sus aristas tienen una etiqueta. Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso.Se usa en el modelado de problemas de la vida real; por ejemplo, al tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.
Grafo mixto	Es aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas
Vértices adyacentes	Son aquellos que conforman un lado o arista. Todo lado conformado por dos vértices se dice que es incidente sobre esos vértices. Si un vértice no tiene otro adyacente se dice que es aislado.
Representación de grafos	Las definiciones y términos presentadas en este texto no están restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso, ya que estos términos tengan una fuerte asociación con dicha representación. Debemos resaltar que una representación diagramática es posible únicamente en casos muy simples.
Representación gráfica de grafos	Los diagramas se pueden representar gráficamente cuando la cantidad de vértices no es grande
Representación de grafos en la computadora Matriz de adyacencia	Cuando la cantidad de vértices es razonablemente grande se puede utilizar una representación para la computadora: matrices. Esta manera de representación permite hacer manipulaciones de un grafo utilizando las operaciones que ofrecen las matrices y en consecuencia determinar,por ejemplo, el grado de un grafo, el camino más corto para ir a un vértice, el número de caminos de longitud n, los ciclos, entre otro
Grado entrante de un vértice	El grado entrante de un vértice es el número de aristas que llegan al vértice.
Grado saliente de un vértice	El grado saliente de un vértice corresponde al número de aristas que salen del vértice.
Grado de un vértice	En los grafos dirigidos el grado total de un vértice es la suma del grado entrante más el grado saliente. En los grafos no dirigidos, el grado total de un vértice es igual al número de aristas que tiene el vértice.
Grafos isomorfos	Isomorfismo significa “de igual forma”. Dos grafos son isomorfos si existe correspondencia uno a uno entre los nodos de ambos grafos, y además conservan la adyacencia tanto entre los nodos como en la dirección de los lados.
Regiones de un grafo plano	Se dice que G es un grafo plano si puede representarse gráficamente sin la intersección de sus aristas. Es decir, un grafo es plano si puede dividirse en regiones no acotadas.
Grafos Homeomorfos	son homeomorfos si pueden reducirse a gráficas isomorfas realizando varias reducciones en serie. La reducción en serie se da cuando en una gráfica las aristas están en serie, y al hacer reducción en serie desaparece Los grafos homeomorfos permiten afirmar cuándo una gráfica no es plana.
Grafos particulares	Es aquél grafo en que existe camino simple entre cualquier par de vértices. Es decir, desde cualquier vértice v tiene al menos un camino para llegar al vértice w. También llamado grafo conectado.
Ejemplo	Grafo disconexo. Grafo regular Grafo completo Grafo fuertemente conexo Grafo no bipartito Grafo Bipartito Completo
autor de TEORÍA DE GRAFOS	Leonhard Paul Euler (1707-1783) Image: Leonhard Euler 2 (binary/octet-stream)

Next up

Terminología de la teoría de grafos

Description

Resource summary

Similar

	Created by DIEGO ARMANDO GARCIA MENDEZ over 4 years ago