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.
== 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.
<syntaxhighlight lang="cpp">
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++)
