24772038
Description
Flashcards by DIEGO ARMANDO GARCIA MENDEZ, updated more than 1 year ago
|
Created by DIEGO ARMANDO GARCIA MENDEZ
over 3 years ago
|
|
| 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) |
Want to create your own Flashcards for free with GoConqr? Learn more.