24026727
Description
Flashcards by Miguel Angel Santiago Marquez, updated more than 1 year ago
|
Created by Miguel Angel Santiago Marquez
almost 4 years ago
|
|
| Question | Answer |
| Qué 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. |
| Grafo Dirigido | Llamado 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. |
| Grafo no dirigido | Tienen un conjunto de aristas E (arcos o lados), tal que cada arista se asocia a un par no ordenado de vértices. |
| Grafo pesado | Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo o un valor de cualquier tipo de dato. |
| Grafo mixto | Es 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. |
| Có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. |
| Matriz de adyacencia | El 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. |
| Grado entrante de un vértice | Número de aristas que llegan al vértice. |
| Grado saliente de un vértice | número de aristas que salen del 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. |
| Grafo Plano | Un grafo plano es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce. |
| Grafos Homeomorfos | Dos grafos G1 y G2 son homeomorfos si pueden reducirse a gráficas isomorfas realizando varias reducciones en serie. |
Want to create your own Flashcards for free with GoConqr? Learn more.