Estruturas Especiais em Dígrafos com Grau de Saída Mínimo Prescrito: Florestas de Ciclos e Feedback Arc Sets
Autores
|
7158 |
3146,3049
|
|
|
7159 |
3146,3049
|
Informações:
Publicações do PESC
Um digrafo D é um par D = (V,A) em que V é um conjunto finito de vértices e A ? V × V é um conjunto de arcos. Um digrafo D que não possui arcos simétricos (isto é, u,v ? V tais que (u,v), (v,u) ? A) é também chamado de orientação de grafo e um torneio é uma orientação de um grafo completo.
O grau de saída de v ? V, denotado por d?(v), é o número de arcos saindo de v, e denotamos por ??(D) o grau de saída mínimo de D, ou seja, o menor número de arcos saindo de um mesmo vértice.
Neste trabalho exploramos dois conceitos em digrafos: Florestas de ciclos e Feedback arc sets.
Uma k-floresta de ciclos é uma coleção de k ciclos C1, C2, . . .,Ck tais que para cada i = 1, . . ., k, o ciclo Ci intercepta a união C1 ? … ? Ci-1 em no máximo um vértice. A Conjectura de Hoàng--Reed afirma que todo digrafo D possui uma ??(D)-floresta de ciclos.
Neste trabalho, nós abordamos esse problema discutindo detalhadamente os artigos que verificam a conjectura para digrafos com grau de saída mínimo 2, 3 e torneios.
Um conjunto de arcos F ? A(D) é um feedback arc set (FAS) se o digrafo obtido de D pela remoção dos arcos em F não contém ciclos. Além disso, um feedback arc set F é minimal se não houver um feedback arc set F' tal que F' ? F. Neste trabalho, exploramos uma conjectura atribuída a Lichiardopol, que diz que todo digrafo D tem um FAS minimal F para o qual o digrafo induzido por F contém um caminho com comprimento (número de arcos no caminho) de pelo menos ??(D). Nós apresentamos a prova para ??(D)=2, construímos uma família de contraexemplos para digrafos com ??(D)? 3 e realizamos testes computacionais para torneios com até dez vértices. Por fim, apresentamos uma demonstração alternativa para a relação de bijeção entre FAS minimais e caminhos hamiltonianos em torneios.
A digraph D is a pair D = (V,A) where V is a finite set of vertices and A ? V × V is a set of arcs. A digraph D that does not have symmetric arcs is also called an orientation of a graph and a tournament is an orientation of a complete graph.
The outdegree of v ? V, denoted by d?(v), is the number of arcs leaving v. We denote by ??(D) the minimum outdegree of D, that is, the smallest number of arcs leaving the same vertex. In this dissertation we study two concepts in digraphs: circuit forests and feedback arc sets.
A k-circuit forest is a collection of k circuits C1, C2, . . .,Ck such that for each i = 1, . . ., k, the circuit Ci intercepts the union C1 ? … ? Ci-1 in at most one vertex. The Hoàng--Reed Conjecture states that every digraph D has a ??(D)-circuit forest. In this work, we study in details the articles that verify the conjecture for digraphs with minimum outdegree 2, 3 and tournaments.
A set of arcs F ? A(D) is a feedback arc set (FAS) if the digraph obtained from D by removing the arcs in F contains no circuits. Also, a feedback arc set F is minimal if there is no feedback arc set F' such that F'? F. In this work, we explore a conjecture attributed to Lichiardopol, which says that every digraph D has a minimal FAS containing a path with a length at least ??(D). We present the proof for ??(D)=2, construct a family of counterexamples for digraphs with ??(D)? 3 and checked it computationally for tournaments with at most ten vertices. Finally, we present an alternative proof for the surprising one to one correspondence between minimal FAS and hamiltonian paths in tournaments.