Teorema de Robbins

Na teoria dos grafos, a Teoria de Robbins, denominada em referência a Herbert Robbins (1939), diz que os grafos que tem uma forte orientação são os grafos de k-arestas-conectado. Isto é, a possibilidade de escolher uma direção para cada aresta de um grafo não direcionado G, transformando-o em um grafo orientado que é um caminho de qualquer vértice para qualquer outro vértice, se e somente se G é conectado e não tem ponte (teoria dos grafos).

Grafos orientados

A caracterização de Robbins dos grafos com fortes orientações talvez seja provada usando decomposição em orelhas, uma ferramenta introduzida por Robbins para esse teste.

Se o grafo tem uma ponte, então ele não pode ser fortemente orientado, não interessa para qual orientação for escolhida para a ponte, não haverá caminho entre um e 2 pontos finais de uma ponte para a outra.

Na outra direção, se for necessário mostrar que todo conectado grafo pode ser fortemente orientado. Como Robbins provou, cada grafo tem uma divisão entre a sequencia de subgrafos chamados "ears", em que o primeiro subgrafo da sequencia é um círculo e cada subgrafo sequente é um caminho, com os 2 caminhos de pontos de fim, ambos começando do mais perto do fim da sequência. Orientar as arestas sem cada fim para que as formas de ciclo direcionado ou caminho direcionado saia de uma forte orientação conectada para o grafo geral.

Resultados relacionados

Um extensão do teorema de Robbins com Grafos mixados por Boesch & Tindell (1980) mostra que, se G é um grafo em que qualquer aresta pode ser direcionada e as outras não direcionadas, e G contém um caminho respeitando as arestas direcionadas de um vértice a outro vértice, então qualquer caminho não direcionado de G que não é uma ponte pode passar a ser direcionado sem mudar a conectividade de G. Em particular, um grafo não direcionado sem caminho pode ser feito de um grafo forte direcionado e conectado for pelo algoritmo guloso, que direciona arestas uma de cada vez para preservar a existência de caminhos entre cada par de vértices. É impossível para qualquer algoritmo ficar preso em uma situação em que nenhuma decisão adicional de orientação pode ser feita.

Algortimos e complexidade

Uma forte orientação de um grafo sem direção pode ser achada em tempo linear pelo algoritmo de busca em profundidade em grafos, orientando todas as arestas no primeira busca profunda da árvore a partir da raiz da árvore, e orientando todas as arestas restantes (que deve necessariamente conectar um antecessor e um descendente na primeira busca profunda) de um descendente para um antecessor. Embora esse algoritmo não seja adequado para computação paralela devido à dificuldade de performance da busca de profundidade neles, algoritmos alternativos são avaliáveis para resolver o problema eficientemente em um modelo paralelo. Algoritmos paralelos são também conhecido para achar uma forte orientação conectada de grafos mixados.