Definición formal de gráfica conexa - [Detalles]

Definimos formalmente lo que es una gráfica conexa y sus componentes. Probamos dos resultados que confirman dos intuiciones claras: (1) que si en una gráfica de orden n todos los vértices tienen grado "grande" entonces la gráfica es conexa; (2) que si una gráfica de orden n tiene "muchas" aristas entonces la gráfica es conexa. En ambos casos se determina de manera exacta el significado de "muchas", en función de n.

Caminos y conexidad - [Detalles]

Notas de apoyo de teoría de gráficas. Este capítulo estudia caminos, ciclos y la noción de conexidad en gráficas.