Cortes dirigidos em grafos

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 for o leque de entrada de um conjunto X de vértices cujo grau de saída de X é zero. 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 leque de saída de V−X.

Dicotomia

Há uma relação muito íntima entre ciclos e cortes dirigidos: Todo arco de qualquer grafo pertence a um ciclo ou a um corte dirigido; e nenhum arco tem as duas propriedades.

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.

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

Exercícios 1

Complete os detalhes da demonstração do teorema da dicotomia.
Suponha que todo arco de um grafo pertence a algum corte dirigido. 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?

Exercícios 2

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 for bipartido dirigido.]