Grafo conexo

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Grafo conexo.
Grafo no conexo

En teoría de grafos, un grafo 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. Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS). En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Conceptos relacionados[editar]

Un grafo dirigido tal que para cualesquiera dos vértices u y v existe un camino dirigido de ida y de regreso se dice que es un 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. todo grafo es dirigido si no tiene flechas.

Solución computacional[editar]

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

Algoritmo[editar]

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;
}

Conexidad en grafos[editar]

En los grafos dirigidos existen 3 tipos de niveles de conexidad por los que se llaman a los grafos como:

  • Conexos: Idéntico a la definición antes vista.
  • Débilmente conexos: Dígrafos que no son conexos pero que sus equivalentes no orientados o sosías sí lo son.
  • Fuertemente conexos: Grafos orientados que entre cualquier par de nodos distintos existe un arco que los une.

Los grafos fuertemente conexos nunca son simples pues exige que siempre entre un par de vértices habrá un par de aristas (una de ida y otra de vuelta).

Tipos[editar]

Grafo dirigido

Un grafo dirigido G, también llamado “dígrafo o digrafo”, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices. Si existe una única arista e asociada con el par ordenado (v, w) de vértices, escribimos e = (v, w) lo cual denota una arista de v a w. En conclusión, se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha.

Un grafo dirigido es aquel que tiene todas sus aristas dirigidas; es decir, un dígrafo está asociado a un par ordenado (vea figura 9.1a). Por ejemplo, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w,v), que es diferente de (v,w). Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.


Grafo no dirigido

Un grafo no dirigido ( consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices. Si existe una única lista e asociada con los vértices v y w, escribimos e = {v,w} ó e = {w,v}. en este contexto, {v,w} denota una arista entre v y w en un grafo no dirigido y no un par ordenado. En conclusión un grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado.

por ejemplo:

si u es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja desordenada {w,v}, que es igual que escribir {v,w}; es decir, {w,v}={v,w}. En tal caso, w es vértice e partida o de llegada; igualmente sucede con v.


Grafo dirigido con peso

Es aquel grafo dirigido en el que sus aristas tienen una etiqueta (vea figura 10.1c). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. Se usa en el modelado de problemas de la vida real; por ejemplo, al tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.

Representación de grafos[editar]

De cualquier manera, para dar algo de sentido a la terminología usada y también para desarrollar algunas ideas intuitivas, se representará un grafo por medio de un diagrama. Ese diagrama se llamará igualmente grafo.

Las definiciones y términos presentadas en este texto no están restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso, ya que estos términos tengan una fuerte asociación con dicha representación. Debemos resaltar que una representación diagramática es posible únicamente en casos muy simples.