Segundo Parcial MD

Question 1

Que es un grafo dual?

Answer 1

un vertice en cada región y los uno a través de las aristas

Question 2

Que es un coloreo propio?

Answer 2

coloreo tal que los extremos de una arista tienen colores distintos

Question 3

Que es el numero cromatico x(G)?

Answer 3

minimo numero de colores necesarios para un coloreo propio

Question 4

Como acotar por arriba x(G)?

Answer 4

dando un coloreo propio

Question 5

Como acotar por abajo x(G)?

Answer 5

en contrando un subgrafo Kn o con ceil(#V / α)

Question 6

Que es un clique?

Answer 6

subconjunto maximal de vertices mutuamente adyacentes

Question 7

Que es clique number?

Answer 7

maximo cardinal de los cliques

Question 8

Que significa que un grafo sea k-critico?

Answer 8

x(G) = k, pero x(G-e) = k-1 para toda arista e

Question 9

Que es un arbol?

Answer 9

Grafo simple conexo sin ciclos

Question 10

Que es una hoja?

Answer 10

en un arbol, un vertice de grado 1

Question 11

Cuantas aristas tiene un arbol con n vertices?

Answer 11

n-1 aristas

Question 12

Que es un bosque?

Answer 12

conjunto de arboles

Question 13

Cuantas aristas tiene un bosque?

Answer 13

n-k, con k la cantidad de componentes conexas

Question 14

Que quiere decir si un grafo es simple con n vertices y
#E > (n-1)(n-2) / 2 ?

Answer 14

que es conexo

Question 14

Que es un arbol con raiz?

Answer 14

un arbol dirigido en el que hay un vertice distinguido r tal que para todo vertice v, existe un camino directo r-v

Question 15

Que es un arbol m-ario

Answer 15

Arbol con raiz en el que todo vertice tiene m o menos hijos

Question 16

Cuantos vertices puede tener un arbol m-ario en el nivel k ?

Answer 16

m^k

Question 17

Cual es la maxima cantidad de vertices que puede tener un arbol m-ario de altura h?

Answer 17

suma de i = 1 hasta h de m^i
osea:
( m^(h+1) - 1 ) / (m - 1)

Question 18

Para que sirve el algoritmo de Huffman?

Answer 18

Es para codificar palabras

Question 19

Como se arma el pre-orden?

Answer 19

1era aparicion

Question 20

Como se arma el post-orden?

Answer 20

ultima aparicion

Question 21

Como se arma el in-orden?

Answer 21

2da aparicion

Question 22

Que es BST?

Answer 22

Binary search tree, un arbol de busqueda en el que:

hijo izq < v < hijo der

Question 23

Cuando un BST esta balanceado?

Answer 23

esta balanceado sii #V del subarbol izq y der difieren a lo sumo en 1

Question 24

Como borrar un elemento de un BST?

Answer 24

si es hoja: se borra
si tiene un unico subarbol hijo: se reemplaza por su hijo
si tiene 2 hijos: reemplazamos por el menor del subarbol derecho

Question 25

Que es una arista frontera?

Answer 25

T subgrafo de G, e es arista forntera si tiene un extremo en T y otro en G-T

Question 26

Que hace el algoritmo BFS ?

Answer 26

Breadth first search, algoritmo que da un arbol recubridor.
elijo la MENOR etiqueta en orden lexicográfico

Question 27

Que hace el algoritmo DFS ?

Answer 27

Depth first search, algoritmo que da un arbol recubridor.
elijo la MAYOR etiqueta (dfnro) en orden lexicográfico.

Question 28

En DFS como se si un vertice es de corte ?

Answer 28

• si es raiz: es de corte si tiene mas de un hijo en T
• si no es raiz: es de corte si tiene un hijo w tal que
  menor(w) >= dnro(v)

Question 29

Que significa menor en DFS?

Answer 29

min{ dfnro(w), a } con a = min{dfnro(vj)},
si existe una arista en G-T {vj, desc(w)}

Question 30

Diferencia entre Prim y Kruskal

Answer 30

En arboles ponderados en las aristas ambos dan un arbol recubridor minimo.
Prim -> elijo aristas fronteras de menor peso
Kruskal -> elijo la arista de menor peso que no forma ciclo

Question 31

Que es una red con capacidad?

Answer 31

digrafo conexo con vertices distinguidos, fuente y sumidero, donde cada arista e tiene una capacidad cap(e) > 0

Question 32

Que es un corte en una red?

Answer 32

dada una particion de vertices Vf, Vs. Un corte son todas las aristas con cola en Vf y cabeza en Vs

Question 33

Que algoritmo se usa para hallar flujo maximo y corte minimo

Answer 33

FFEK