Grafo conexo

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

Conceptos relacionados

Un grafo dirigido tal que para cualesquiera dos vértices u y v 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;
}