13522255
Description
Mind Map by Josue Norato, updated more than 1 year ago
|
Created by Josue Norato
almost 8 years ago
|
|
GRAFOS
- Un grafo es un conjunto, no vacío, de objetos llamados
vértices (o nodos) y una selección de pares de vértices,
llamados aristas (edges en inglés) que pueden ser
orientados o no.
- Estructura de lista
- Lista de incidencia: El grafo está representado por una matriz de
A (aristas) por V (vértices), donde [arista, vértice] contiene la
información de la arista (conectado o no conectado).
- Lista de adyacencia: El grafo está representado por un arreglo de
listas de adyacencia. Para un vértice i, la lista de adyacencia está
formada por todos los vértices adyacentes a i. Puede construirse
en tiempo lineal, y las inserciones pueden hacerse al principio de
cada lista, con lo que se asegura tiempo constante.
- Lista de grados: También llamada secuencia de grados o
sucesión gráfica de un una secuencia de números, que
corresponde a los grados de los vértices del grafo.
- Lista de incidencia: El grafo está representado por una matriz de
A (aristas) por V (vértices), donde [arista, vértice] contiene la
información de la arista (conectado o no conectado).
- Estructuras matriciales
- 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.
- Matriz de incidencia: El grafo está
representado por una matriz de A (aristas)
por V (vértices), donde [vértice, arista]
contiene la información de la arista (1 -
conectado, 0 - no conectado)
- 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.
- Estructura de lista
- Definiciones
- En teoría de grafos, sólo queda lo esencial del
dibujo: la forma de las aristas no son
relevantes, sólo importa a qué vértices están
unidas. La posición de los vértices tampoco
importa, y se puede variar para obtener un
dibujo más claro.
- Los vértices constituyen uno de los dos
elementos que forman un grafo. Como ocurre
con el resto de las ramas de las matemáticas,
a la Teoría de Grafos no le interesa saber qué
son los vértices.
- En teoría de grafos, sólo queda lo esencial del
dibujo: la forma de las aristas no son
relevantes, sólo importa a qué vértices están
unidas. La posición de los vértices tampoco
importa, y se puede variar para obtener un
dibujo más claro.
- Caracterización de grafos
- Grafos simples Un grafo es simple si a lo más existe una
arista uniendo dos vértices cualesquiera. Esto es
equivalente a decir que una arista cualquiera es la única
que une dos vértices específicos. Un grafo que no es
simple se denomina multigrafo.
- Grafos conexos Un grafo es conexo si cada par de
vértices está conectado por un camino; es decir, si
para cualquier par de vértices (a, b), existe al menos
un camino posible desde a hacia b. Un grafo es
doblemente conexo si cada par de vértices está
conectado por al menos dos caminos disjuntos; es
decir, es conexo y no existe un vértice tal que al
sacarlo el grafo resultante sea disconexo.
- Grafos completos Un grafo es completo si
existen aristas uniendo todos los pares posibles
de vértices. Es decir, todo par de vértices (a, b)
debe tener una arista e que los une.
- Grafos bipartitos Un grafo G es bipartito si
sus vértices son la unión de dos grupos de
vértices
- Grafos simples Un grafo es simple si a lo más existe una
arista uniendo dos vértices cualesquiera. Esto es
equivalente a decir que una arista cualquiera es la única
que une dos vértices específicos. Un grafo que no es
simple se denomina multigrafo.
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.