Grafo conexo

En teoría de grafos, un grafo $G$ se dice conexo si, para cualquier par de vértices a y b en G, existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de a a b.

Conceptos relacionados

Un grafo dirigido tal que para cualesquiera dos vértices a y b existe un camino dirigido de ida y de regreso se dice grafo fuertemente conexo.

Un conjunto de corte de vértices U en un grafo G, es un conjunto de vértices de G, tal que G-U no es conexo o trivial. Similarmente, un conjunto de corte de aristas F es un conjunto de aristas tal que G-F no es conexo.

Solución computacional

El problema computacional de determinar si un grafo es conexo puede ser resuelto con algunos algoritmos como el MFMC (max-flow, min-cut).

Algoritmo

Ejemplo de algoritmo iterativo implementado en C++ para determinar si un grafo es conexo utilizando búsqueda en profundidad, donde _n es la cantidad de vértices y _graph denota la matriz de adyacencia.

bool Graph::is_connected()
{
    if (_n <= 1)
        return true;
 
    vector<bool> visit(_n);
    vector<bool>::iterator iter;
 
    for(iter = visit.begin(); iter != visit.end(); iter++)
        *iter = false;
 
    set<int> forvisit;
    set<int>::iterator current;
 
    forvisit.insert(0);
    while (!forvisit.empty())
    {
        current = forvisit.begin();     
        if (!visit[*current])
        {
            for (int i = 0; i < _n; i++)
            {
                if (_graph[*current][i] == 1 && !visit[i])
                    forvisit.insert(i);
            }
        }
        visit[*current] = true;
        forvisit.erase(current);
    }
 
    bool result;
    for (iter = visit.begin(); iter != visit.end(); iter++)
        result = result && *iter;
    return result;
}