Grafos

Question 1

¿Que son los Grafos?

Answer 1

Son estructuras discretas que aparecen en cada disciplina donde se requiere modelar algo.

Son mapas conceptuales que ayudan a representar el conocimiento.

Question 2

¿Cuales son las Propiedades de los Grafos?

Answer 2

ADYACENCIA
INCIDENCIA
PONDERACIÓN
ETIQUETADO

Question 3

Defina la propiedad de Adyacencia

Answer 3

ADYACENCIA
2 aristas son adyacentes si tienen un vértice en común;
2 vértices son adyacentes si una arista los une.

Question 4

Defina la propiedad de Incidencia

Answer 4

INCIDENCIA

Una arista es incidente a un vértice si ésta lo une a otro.

Question 5

Defina la propiedad de Ponderacion

Answer 5

PONDERACIÓN

Se le asocia a cada arista un valor (costo, peso, longitud, etc) con el fin de aumentar la expresividad del modelo.

Question 6

Defina la propiedad de Etiquetado

Answer 6

ETIQUETADO

Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Question 7

¿Cómo se compone un Grafo?

Answer 7

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

Question 8

El orden de un Grafo G es…

Answer 8

El orden de un Grafo G es…

el número de vértices ⇒ G = |V|

Question 9

El grado de un vértice v ∈ V es…

Answer 9

El grado de un vértice v ∈ V es

igual al número de aristas que inciden en él.

Question 10

Describa Vertices (Nodos)

Answer 10

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.

Question 11

Describa Aristas (Arcos) y sus tipos

Answer 11

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.

Question 12

¿Que es un Grafo Ponderado?

Answer 12

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.

Question 13

Adyacencia e Incidencia en un Grafo Dirigido

Answer 13

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.

Question 14

Incidencia en Grafos no Dirigidos

Answer 14

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.

Question 15

Elementos de un grafo dirigido o digrafo:

Answer 15

• 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).

Question 16

Defina un arco en un grafo dirigido

Answer 16

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"

Question 17

Adyacencia / Incidencia en un grafo dirigido

Answer 17

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)

Question 18

Lazo de un dígrafo y sus propiedades

Answer 18

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.

Question 19

Grado de un vértice (nodo)

Answer 19

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|

Question 20

Grafos simples

Answer 20

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)}

Question 21

Multigrafos

Answer 21

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)}

Question 22

Pseudografos

Answer 22

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)}

Question 23

Definición de Caminos o cadenas

Answer 23

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.

Question 24

Los 4 Tipos de Caminos son:

Answer 24

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.

Question 25

Matriz de adyacencia

Answer 25

La matriz de adyacencia para G es una matriz A de dimensión nxn, donde las entradas A[i,j] cuentan el números de arcos que van del vértice i (nodo inicial) al j (nodo terminal).

Ag no es simétrica en general.
Si G es un grafo simple => Aii = 0 y Aij E {0,1}
Si G es un multigrafo Aii = 0.