Flashcards
Terminología Teoría de los Grafos
Cards in this deck (12)
- 1Qué es un Grafo?Un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
- 2Grafo DirigidoLlamado también dígrafo tienen un conjunto de vértices V (nodos) y un conjunto de aristas E (arcos o lados), tal que cada arista se asocia a un par ordenado de vértices.
- 3Grafo no dirigidoTienen un conjunto de aristas E (arcos o lados), tal que cada arista se asocia a un par no ordenado de vértices.
- 4Grafo pesadoUn grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo o un valor de cualquier tipo de dato.
- 5Grafo mixtoEs aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.
- 6Cómo se representan los Grafos?Existen diferentes formas de representar un grafo, y hay muchos métodos para almacenarlos en una computadora. La estructura de datos usada dependerá de las características del grafo, y el algoritmo usado para manipularlo. Entre las más comunes esta las listas y matrices, con frecuencia se usa una combinación de ambas.
- 7Matriz de adyacenciaEl grafo está representado por una matriz cuadrada M de tamaño n^2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento m_ {x, y} es 1, de lo contrario, es 0.
- 8Grado entrante de un vérticeNúmero de aristas que llegan al vértice.
- 9Grado saliente de un vérticenúmero de aristas que salen del vértice.
- 10Grafos 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.
- 11Grafo PlanoUn grafo plano es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce.
- 12Grafos HomeomorfosDos grafos G1 y G2 son homeomorfos si pueden reducirse a gráficas isomorfas realizando varias reducciones en serie.
Information
- Description
- Flashcards on Terminología Teoría de los Grafos, created by Miguel Angel Santiago Marquez on 30/06/2020.
- Created by
- Miguel Angel Santiago Marquez
- Views
- 151
- Tags
- Rating