Diferencia entre los gráficos conectados vs fuertemente conectados vs completos

Question

Cuál es la diferencia entre

conectado

fuertemente conectado y

¿completar?

Mi entendimiento es:

conectado : se puede llegar a cada vértice desde cualquier otro vértice.

fuertemente conectado : cada vértice tiene un borde que lo conecta a cada otro vértice.

completo : igual que fuertemente conectado.

¿Es esto correcto?

Answer 1

• Conectado suele asociarse con gráficos no dirigidos (bordes de dos vías): hay un camino entre cada dos nodos.
• Fuertemente conectado normalmente se asocia con gráficos dirigidos (bordes unidireccionales): hay una ruta entre cada dos nodos.
• Los gráficos completos son gráficos no dirigidos donde hay un borde entre cada par de nodos.

Answer 2

También es importante recordar la distinción entre firmemente conectado de forma unilateral y conectado. Un grafo dirigido es unilateralmente conectado si para cualquier par de vértices a y b, hay una trayectoria de a a b o de b a a, pero no necesariamente ambos (aunque podría ser). Fuertemente conectados implica que ambas dirigidas rutas de acceso. Esto significa que está firmemente conectado gráficos son un subconjunto de forma unilateral conectado gráficos.

Y un grafo dirigido es débilmente conectado si subyacente del gráfico está conectado.