Grafo conexo

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.

Definiciones Relacionadas

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 actual;
 
    forvisit.insert(0);
    while( !forvisit.empty() )
    {
        actual = (forvisit.begin());     
        if( visit[*actual] == false )
        {
            for(int i=0;i<_n;i++)
            {
                if( _graph[*actual][i] == 1 && !visit[i])
                    forvisit.insert(i);
            }
        }
        visit[*actual]= true;
        forvisit.erase(actual);
    }
 
    bool result;
    for(iter=visit.begin();iter!= visit.end();iter++)
        result = result && *iter;
    return result;
}

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Conexo — puede referirse, en general, a algo que está conectado a otra cosa. De forma, más específica, puede referirse a los siguientes conceptos matemáticos: Espacio conexo, en topología, un espacio topológico que no se puede representar como unión de… …   Wikipedia Español

  • Grafo plano — Grafos de ejemplo Plano No plano …   Wikipedia Español

  • Grafo — Para otros usos de este término, véase Grafo (desambiguación). Para la teoría en torno a este objeto matemático, véase Teoría de grafos. Grafo etiquetado con 6 vértices y 7 aristas. En matemáticas y ciencias de la computación, un grafo (del …   Wikipedia Español

  • Grafo nulo — Vértices 0 Aristas 0 Cintura (girth) …   Wikipedia Español

  • Grafo ciclo — Ciclo Cn C6: Un Grafo Ciclo de longitud 6. Vertices: n Aristas: n …   Wikipedia Español

  • Componente fuertemente conexo — Un grafo dirigido, y sus componentes fuertemente conexos. En la Teoría de los grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes… …   Wikipedia Español

  • Espacio conexo por caminos — En topología un espacio topológico se dice que es conexo por caminos si dos elementos cualesquiera pueden conectarse mediante una curva. Definición Sea un espacio topológico. Una curva en X es una función continua . (En realidad, puede ser… …   Wikipedia Español

  • Componente fuertemente conexo — En la Teoría de los grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus sub …   Enciclopedia Universal

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”