Download grafos - Universidad Nacional de Lanús

UNIVERSIDAD NACIONAL DE LANUS
LICENCIATURA EN SISTEMAS
Fundamentos de Teoría de la Computación
Prof. Tit.: Dr. Ramón García-Martínez
JTP:
Lic. Darío Rodríguez
GUIA DE ESTUDIO
GRAFOS
Material “Grafos” (anónimo)
1. Defina “conjunto”, “elemento”.
2. Defina como se denota la “pertenencia” y “no pertenencia” de un “elemento” a un
“conjunto”.
3. Defina “subconjunto”, “inclusión de un conjunto en otro”, “igualdad entre conjuntos” e
“inclusión propia”.
4. Defina “Producto Cartesiano”.
5. Defina “relación”, “esta relacionado con” y “relación binaria”.
6. Defina las propiedades de: “relación reflexiva”, “relación simétrica”, “relación antisimétrica”.
7. Defina “relación de equivalencia” y “clase de equivalencia”.
8. Enuncie la propiedad mas importante de las “relaciones de equivalencia”.
9. Defina “relación de orden parcial”.
10. Defina “clausura transitiva”.
11. Defina “grafo”, “nodo” y “arco”.
12. Defina “grafo dirigido” o “digrafo”.
13. Defina “bucle” o “lazo”.
14. Defina “multigrafo” y “multigrafo dirigido”.
15. Defina “vértice inicial”, “vértice final” y “vértices extremos”.
16. Defina “grado”, “grado de entrada” y “grado de salida”.
17. Defina “matriz de adyacencia”.
18. Defina “lista de adyacencia”.
19. Defina “matriz de incidencia”.
20. Defina “camino de longitud k”.
21. Defina “longitud del camino”.
22. Defina “camino simple”.
23. Defina “ciclo”.
24. Defina “vértice accesible”.
25. Defina “grafo conexo” y “grafo fuertemente conexo”.
26. Defina “grafo completo”.
27. Defina “torneo”.
28. Defina “grafo bipartito”.
29. Defina “camino de longitud n” y “ciclo de longitud n”.
30. Defina “grafo cúbico”. Ejemplifique.
31. Defina “arbol” y “bosque”. Ejemplifique.
32. Enuncie afirmaciones equivalentes relativas a grafos no dirigidos.
33. Defina “árbol enraizado”.
34. Defina “antecesor”, “descendiente”, “antecesor propio” y “descendiente propio”.
35. Defina “subárbol con raíz en v”.
36. En el contexto de grafos y arboles, defina “padre”, “hijo”, “hermano”, “hoja o nodo
externo”, “nodo interno”, “grado de un nodo” y “árbol m-ario”.
37. Defina “profundidad de un nodo” y “altura de un árbol”.
38. Defina “árbol ordenado”.
39. Defina “árbol binario”.
40. Defina “recorrido de un grafo”.
41. Defina notación: “infija”, “postfija”, “prefija”.
42. Desarrolle los algoritmos de “preorden”, “postorden” y "inorden". Con que notación se
asocia cada uno
43. Dado el grafo:
Describa como se recorrerían los nodos de manera: inorden, preorden y postorden.
44. Defina “recorrido euleriano” y “circuito euleriano”.
45. Defina “grafo euleriano”.
46. Enuncie el teorema de Euler sobre grafos.
47. Enuncie el corolario del teorema de Euler sobre grafos.
48. Enuncie el teorema conocido como el "lema del apretón de manos".
49. Defina “camino hamiltoniano” y “ciclo hamiltoniano”.
50. Defina la relación entre “torneo ” y “camino hamiltoniano”.
51. Describa conceptualmente el recorrido de vértices en "profundidad" de un grafo.
52. Desarrolle los algoritmos de recorrido “en profundidad" y “en profundidad no recursivo".
53. Describa conceptualmente el recorrido de vértices en "anchura" de un grafo.
54. Desarrolle el algoritmo de recorrido “en anchura".
55. Defina “árbol abarcador” en el contexto de recorrido en anchura.
56. Defina “cola de prioridad”.
57. Defina “red”, “peso o coste” y “coste asociado a un camino”.
58. Defina “camino mínimo”.