Grafos Flashcards
¿Que son los Grafos?
Son estructuras discretas que aparecen en cada disciplina donde se requiere modelar algo.
Son mapas conceptuales que ayudan a representar el conocimiento.
¿Cuales son las Propiedades de los Grafos?
ADYACENCIA
INCIDENCIA
PONDERACIÓN
ETIQUETADO
Defina la propiedad de Adyacencia
ADYACENCIA
2 aristas son adyacentes si tienen un vértice en común;
2 vértices son adyacentes si una arista los une.
Defina la propiedad de Incidencia
INCIDENCIA
Una arista es incidente a un vértice si ésta lo une a otro.
Defina la propiedad de Ponderacion
PONDERACIÓN
Se le asocia a cada arista un valor (costo, peso, longitud, etc) con el fin de aumentar la expresividad del modelo.
Defina la propiedad de Etiquetado
ETIQUETADO
Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.
¿Cómo se compone un Grafo?
Un grafo G consiste en:
- Un conjunto no vacío de vértices o nodos V, y
- Un conjunto de arcos o aristas E
- G = (V, E)
Cada e ∈ E (arista de E) tiene un par (v1, v2) ∈ V x V asociado es decir, e conecta v1 con v2
El orden de un Grafo G es…
El orden de un Grafo G es…
el número de vértices ⇒ G = |V|
El grado de un vértice v ∈ V es…
El grado de un vértice v ∈ V es
igual al número de aristas que inciden en él.
Describa Vertices (Nodos)
Elementos (objetos) que forman un grafo. Cada uno lleva asociada un grado característico según la situación, que se corresponde con la cantidad de arcos o aristas que confluyen en dicho vértice.
Describa Aristas (Arcos) y sus tipos
Son relaciones entre los elementos que forman el grafo. Existen los siguientes tipos:
RAMAS: Arcos o aristas que unen un vértice con otro.
PARALELAS (múltiples): Arcos o aristas conjuntas si el vértice inicial y final son el mismo.
CÍCLICAS (lazo, bucle). Arco o arista que el vértice inicial y final es el mismo.
¿Que es un Grafo Ponderado?
Un grafo ponderado G=(V,E,w) es un grafo en el que a cada arco o arista e E E se le asocia un peso w(e) E R.
Adyacencia e Incidencia en un Grafo Dirigido
En un grafo dirigido, un vértices es adyacente a otro si están conectados por un arco (cola → cabeza)
El vértice cola es incidente al vértice cabeza.
El vértice cabeza es adyacente al vértice cola.
Incidencia en Grafos no Dirigidos
En un grafo no dirigido, dos vértices son adyacentes si están conectados por una arista.
En tal caso, cada uno de estos vértices es incidente en dicha arista.
Elementos de un grafo dirigido o digrafo:
- Un grafo dirigido o digrafo G consiste en un conjunto no vacío de vértices V y un conjunto de arcos E → G = (V, E).
Defina un arco en un grafo dirigido
Un arco es un par ordenado de vértices (v, w) v es la cola (nodo inicial) y w es la cabeza (nodo terminal) del arco. El arco (v, w) se expresa a menudo como v → w y se dice que "va de v a w"
Adyacencia / Incidencia en un grafo dirigido
En un arco v → w:
- el arco v → w es incidente en el vértice v (vertice cola).
- w (vertice cabeza) es adyacente a v (vertice cola)
Lazo de un dígrafo y sus propiedades
Cuando un arco es un par ordenado de vértices idénticos se llama lazo, un arco que une un vértice consigo mismo. El lazo (v,v) se expresa a menudo como v → v
Propiedades:
- v es adyacente a v
- el arco v → v es incidente en el vértice v.
Grado de un vértice (nodo)
El grado de entrada (interno) de v es el número de arcos que tienen como nodo terminal a v y se denota por g-(v).
El grado de salida (externo) de v es el número de arcos que tienen como nodo inicial a v y se denota por g+(v).
La sumatoria de todos los g-(v) es igual a la sumatoria de los g+(v), o sea, la cantidad de arcos |E|
Grafos simples
Grafo simple G = (V,E)
- conjunto no vacío de vértices V
- conjunto de arcos E, donde se tiene un conjunto de pares de elementos distintos de V.
- V= {1,2,3,4}
- E = {(1,2),(1,3),(2,4),(3,2),(4,3)}
Multigrafos
Multigrafos G = (V,E)
- conjunto no vacío de vértices V
- conjunto de arcos E, en el que se permite que haya arcos múltiples (arcos paralelos, aquellos que conectan el mismo par de vértices).
- V= {1,2,3,4}
- E = {(1,2),(1,2),(1,3),(2,4),(3,2),(4,3)}
Pseudografos
Pseudografos G = (V,E)
- conjunto no vacío de vértices V
- conjunto de arcos E, en el que se permite que haya arcos múltiples (arcos paralelos) y lazos (arcos cíclicos).
- V= {1,2,3,4}
- E = {(1,2),(1,2),(1,3),(2,4),(3,2),(3,3),(4,3)}
Definición de Caminos o cadenas
Un camino o cadena en un grafo dirigido es una secuencia de vertices y los arcos que conectan un vertice con el siguiente.
- La longitud de un camino es el número de arcos en ese camino. (Caso especial: un vértice sencillo v solo es un camino de longitud 0, si no tiene lazos)
- Se pueden repetir vértices y arcos.
Los 4 Tipos de Caminos son:
CAMINO SIMPLE es un camino en donde todos los arcos son distintos (se pueden repetir vértices).
CIRCUITO es un camino simple cerrado de longitud por lo menos uno, es decir, que empieza y termina en el mismo vértice (se pueden repetir vértices).
CAMINO ELEMENTAL es un camino simple en donde todos los vértices son distintos, excepto tal vez el primero y el último.
CICLO es un camino elemental cerrado de longitud por lo menos uno, es decir, que empieza y termina en el mismo vértice.
