JUA - Campus Juazeiro

Navegar

Agora exibindo 1 - 1 de 1

Uma demonstração matricial do Teorema de König (sem o uso de grafos)
(2026-11-05) Saavedra, Beto; Kuzimoto, Diego
This work presents a matrix-based proof of König’s Theorem without relying on graph theory, taking as its starting point the mathematical foundations of the Hungarian Method for solving optimal assignment problems. Initially, the concepts of cost matrix, optimal assignment, and equivalence between matrices are introduced, accompanied by an application illustrating the main steps of the algorithm. Subsequently, the termination of the procedure and the determination of optimal solutions are discussed. The proof of König’s Theorem is developed through a matrix-based approach, using auxiliary notation and a result referred to as **Diego’s Lemma**. This text was prepared as supporting material for the short course **MC55 – A Matrix-Based Proof of König’s Theorem Without Using Graph Theory**, delivered during the **12th Biennial Meeting of the Brazilian Mathematical Society**, held at the Federal University of Rio Grande do Norte (UFRN), in Natal, Brazil, from August 3 to 7, 2026, with a total duration of four hours. The presentation aims to provide an alternative perspective on understanding König’s Theorem and its relationship with the Hungarian Method, emphasizing elementary matrix-based arguments.