Determinação de grafos via matróides

Abstract

Um matróide M é um par ordenado (E, I), onde E = {1, . . . , n} e I é uma coleção de subconjuntos de E tais que: (i) ∅ ∈ I; (ii) I ∈ I, I 0 ⊂ I =⇒ I 0 ∈ I; (iii) I1 , I2 ∈ I, |I1 | < |I2 | =⇒ existe e ∈ I2 \ I1 tal que I1 ∪ e ∈ I. [...]