Graf connex

En la teoria de grafs, un graf relacionat o connectat^[1] és un graf en el qual tots els seus vèrtexs estan connectats per una ruta (si el graf no està dirigit)^[2] o per un semi-camí (si el graf està dirigit). Un graf que no està relacionat s’anomena disconnex o graf no connectat. Els subgrafs màxims relacionats amb un graf no dirigit s’anomenen components connexos.^[1] En el cas dels grafs dirigits, si no es considera el significat de les arestes, hi ha un component dèbilment relacionat, mentre que es considera el significat, es parla de components fortament relacionats.

Un graf està doblement relacionat si cada parell de vèrtexs està connectat per almenys dues rutes disjuntes; És a dir, està relacionat i no té vèrtexs de tall, és a dir, vèrtexs de manera que quan s'eliminen el graf resultant es converteix en disconnex.

En informàtica, és possible determinar si un graf està relacionat amb un algorisme de cerca en amplada (BFS) o de cerca en profunditat (DFS). En termes matemàtics, la propietat d’un graf d'ésser relacionat (fortament) permet establir basada en una relació d’equivalència per als seus vèrtexs, que condueix a una partició d’aquests en components (fortament) relacionats quan es consideren grafs aïllats. Aquesta propietat és important per a moltes demostracions en la teoria de grafs.