Doido Dev

Resolução do Problema de Emparelhamento Máximo em Grafos Bipartidos Dado um grafo bipartido com duas partições: uma à esquerda contendo n1 vértices (numerados de 1 a n1) e outra à direita com n2 vértices (de 1 a n2), e um total de m arestas conectando vértices das duas partes, o objetivo é determinar o número máximo de arestas que podem ser sel ...

Descrição O governante Windy deseja formar um exército. Ele pode recrutar N mulheres e M homens, pagando 10.000 RMB por cada soldado sem vantagens especiais. Existem relações entre alguns pares de mulher-homem. Se uma relação com desconto d existir e um dos endivíduos já estiver recrutado, o outro pode ser recrutado por 10.000 - d RMB. Cada rel ...

Fundametnos de Grafos Bipartidos Um grafo é bipartido se e somente se não contém ciclos de comprimento ímpar. Um método eficiente para verificar essa propriedade é a coloração por busca em profundidade (DFS). A ideia é tentar atribuir dois rótulos (0 ou 1) aos vértices de modo que vértices adjacentes tenham rótulos diferentes. Se em algum momen ...