Flashcards
Terminología de la teoría de grafos
Cards in this deck (19)
- 1INTRODUCCIÓNLeonhard 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
- 2Concepto de grafosea 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.
- 3Grafo dirigidoUn 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 - 4Grafo no dirigidoUn 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).
- 5Grafo dirigido con pesoes 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.
- 6Grafo mixtoEs aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas
- 7Vértices adyacentesSon 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.
- 8Representación de grafosLas 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.
- 9Representación gráfica de grafosLos diagramas se pueden representar gráficamente cuando la cantidad de vértices no es grande
- 10Representación de grafos en la computadora Matriz de adyacenciaCuando 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
- 11Grado entrante de un vérticeEl grado entrante de un vértice es el número de aristas que llegan al vértice.
- 12Grado saliente de un vérticeEl grado saliente de un vértice corresponde al número de aristas que salen del vértice.
- 13Grado de un vérticeEn 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.
- 14Grafos isomorfosIsomorfismo 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.
- 15Regiones de un grafo planoSe 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.
- 16Grafos Homeomorfosson 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.
- 17Grafos particularesEs 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.
- 18EjemploGrafo disconexo.
Grafo regular
Grafo completo
Grafo fuertemente conexo
Grafo no bipartito
Grafo Bipartito Completo - 19autor de TEORÍA DE GRAFOSLeonhard Paul Euler
(1707-1783)
Information
- Description
- términos y conceptos usados en la teoría de grafos.
- Created by
- DIEGO ARMANDO GARCIA MENDEZ
- Views
- 28
- Tags
- Rating