Graph Theory Review

Se cubren las nociones y definiciones básicas relacionadas con los grafos dirigidos y no dirigidos, el movimiento en un grafo y la conectividad, así como la aparición de una componente conexa gigante en muchas redes reales. A continuación, describimos familias de grafos clásicas que incluyen grafos completos, regulares, bipartitos, árboles y planares. Nos resultaran de gran utilidad las nociones de teoría algebraica de grafos, como la matriz adyacencia, la matriz de incidencia y el Laplaciano de un grafo, sus relaciones y propiedades espectrales. Terminamos con algoritmos y estructuras de datos para grafos y describimos breadth-first-search (BFS) para, por ejemplo, calcular distancias desde un vértice determinado.