- 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; }
Categoría:- Familias de grafos
Wikimedia foundation. 2010.
