| Conceptos básicos |
Conceptos básicos: tipos de grafos (grafos simples, digrafos, multigrafos, hipergrafos), isomorfismos, subgrafos, secuencias gráficas y teorema de Havel-Hakimi.
Algunos invariantes en grafos simples (número de dominación, diferencial de un grafo, número de independencia, número de cubrimiento de vértices, 2-packing, etc) |
Operaciones con grafos
|
Operaciones con grafos: Unión, suma, producto cartesiano, producto corona, producto fuerte, producto lexicográfico, grafo línea, grafos Sierpinski generalizados. |
| Recorridos, conectividad y distancia |
Recorridos, conectividad y algoritmos de exploración de grafos, grafos eulerianos, grafos hamiltonianos, distancia y algoritmos relacionados, problema de la dimensión métrica y sus variantes, árboles (caracterización, propiedades, árboles con raíz, exploración de árboles binarios, árbol generador). |
| Emparejamiento, planaridad y coloración |
Emparejamiento y emparejamiento perfecto, grafos planares y teorema de Kuratowski, coloración de grafos y polinomio cromático. |
Asignaturas
