GRAFOS: Cortes dirigidos

Um corte dirigido em um grafo é o conjunto de todos os arcos que entram em um sorvedouro. Todo corte dirigido é, também, o conjunto dos arcos que saem de uma fonte.

Em outras palavras, um conjunto C de arcos é um corte dirigido se existe um conjunto X de vértices tal que o grau de saída de X é zero e C é o fan-in de X. Se V é o conjunto de todos os vértices do grafo então é evidente que o grau de entrada de V–X é zero e C é o fan-out de V–X.

Dicotomia

Esse fato é conhecido como teorema da dicotomia. A prova do teorema é muito fácil: tome um arco (v,w) e considere o território, digamos T, de w ; se v está em T então o arco pertence a um ciclo; senão, o arco pertence a um corte dirigido.

Conseqüência imediata do teorema: um grafo é acíclico se e só se cada um de seus arcos pertence a algum corte dirigido.

Exercícios

Complete os detalhes da demonstração do teorema da dicotomia.
Suponha que todo arco de um grafo pertence a algum corte orientado. Mostre que o grafo tem uma numeração topológica.
Suponha que um grafo tem uma numeração topológica. Para cada arco (v,w) do grafo, exiba um corte dirigido que contém o arco.
Mostre que um grafo é bipartido dirigido se e só se o conjunto de todos os arcos é um corte dirigido.
Escreva um algoritmo que receba um arco a de um grafo g e decida se a pertence a um ciclo ou a um corte dirigido.
Que "cara" tem um grafo sem cortes dirigidos?

Mais problemas relacionados com cortes

Invente um algoritmo que receba um arco a de um grafo g e encontre um corte dirigido mínimo (número mínimo de arcos) dentre os que contêm a.
[Desafio] Invente um algoritmo que receba um arco a de um grafo g e encontre um corte dirigido máximo (número máximo de arcos) dentre os que contêm a. [Esse problema é muito fácil se o grafo é bipartido dirigido.]