DUAL PADA MATROID

Abstract

Misal himpunan berhingga dan Ĩ koleksi himpunan bagian dari yang memenuhi 3 syarat. Pasangan himpunan terurut dan yang ditulis ( ) disebut matroid. Himpunan bebas maksimal pada matroid disebut basis. Himpunan tak bebas minimal pada matroid disebut sirkit. Untuk , rank dari yang dinotasikan ( ) adalah ( ) maksimum *| | +. Rank dari matroid yang dinotasikan sebagai ( ) adalah rank dari himpunan . Dapat dibentuk dual matroid dengan menggunakan ( ) koleksi basis dari sebuah matroid pada himpunan . Basis dari disebut kobasis dari , sirkit dari disebut kosirkit dari , dan rank dari disebut korank dari . Untuk semua berlaku ( ) | | ( ) ( ), jika maka ada sebuah basis dengan dan . Subset dari adalah basis dari jika dan hanya jika adalah subset minimal yang mempunyai irisan tak kosong dengan setiap kosirkit dari . Subset dari adalah sebuah sirkit dari jika dan hanya jika adalah subset minimal yang mempunyai irisan tak kosong dengan setiap kobasis dari . Matroid adalah dual pada matroid , sedangkan matroid adalah dual pada matroid
Kata kunci : matroid dan dual matroid, basis, sirkit, rank, kobasis, kosirkit, korank