Segundo Parcial MD Flashcards
Que es un grafo dual?
un vertice en cada región y los uno a través de las aristas
Que es un coloreo propio?
coloreo tal que los extremos de una arista tienen colores distintos
Que es el numero cromatico x(G)?
minimo numero de colores necesarios para un coloreo propio
Como acotar por arriba x(G)?
dando un coloreo propio
Como acotar por abajo x(G)?
en contrando un subgrafo Kn o con ceil(#V / α)
Que es un clique?
subconjunto maximal de vertices mutuamente adyacentes
Que es clique number?
maximo cardinal de los cliques
Que significa que un grafo sea k-critico?
x(G) = k, pero x(G-e) = k-1 para toda arista e
Que es un arbol?
Grafo simple conexo sin ciclos
Que es una hoja?
en un arbol, un vertice de grado 1
Cuantas aristas tiene un arbol con n vertices?
n-1 aristas
Que es un bosque?
conjunto de arboles
Cuantas aristas tiene un bosque?
n-k, con k la cantidad de componentes conexas
Que quiere decir si un grafo es simple con n vertices y
#E > (n-1)(n-2) / 2 ?
que es conexo
Que es un arbol con raiz?
un arbol dirigido en el que hay un vertice distinguido r tal que para todo vertice v, existe un camino directo r-v
Que es un arbol m-ario
Arbol con raiz en el que todo vertice tiene m o menos hijos
Cuantos vertices puede tener un arbol m-ario en el nivel k ?
m^k
Cual es la maxima cantidad de vertices que puede tener un arbol m-ario de altura h?
suma de i = 1 hasta h de m^i
osea:
( m^(h+1) - 1 ) / (m - 1)
Para que sirve el algoritmo de Huffman?
Es para codificar palabras
Como se arma el pre-orden?
1era aparicion
Como se arma el post-orden?
ultima aparicion
Como se arma el in-orden?
2da aparicion
Que es BST?
Binary search tree, un arbol de busqueda en el que:
hijo izq < v < hijo der
Cuando un BST esta balanceado?
esta balanceado sii #V del subarbol izq y der difieren a lo sumo en 1