Hubungan Graf, Ruang Kebebasan, dan Dual Graf Pada Struktur Cycle dan Struktur Cutset

Abstract

Ruang kebebasan adalah suatu ruang yang pembentukannya berdasarkan konsep sifat bebas linear dan konsep graf. Ruang kebebasan terdiri dari koleksi himpunan bebas-himpunan bebas yang merupakan himpunan bagian dari suatu himpunan berhingga, dan himpunan berhingga itu sendiri secara umum dapat dikatakan mirip dengan himpunan sisi pada graf. Himpunan bagian yang bukan himpunan bebas disebut himpunan takbebas. Koleksi himpunan bebas-himpunan bebas disebut struktur kebebasan. Himpunan bebas maksimal disebut basis dan himpunan takbebas minimal disebut sirkuit. Dari sebuah graf terhubungkan dapat diperoleh dua buah struktur kebebasan yaitu struktur cycle dan struktur cutset. Struktur cycle adalah himpunan sisi yang tidak memuat cycle, sedangkan struktur cutset adalah himpunan sisi yang tidak memuat cutset. Koleksi basis dari struktur cicle merupakan spanning Tree-spanning Tree pada graf, sedangkan koleksi basis dari struktur culset "merupakan komplemenkomplemen dari spanning Iree. Dengan melihat basis, hubungan graf dan fuang kebebasan dapat dinyatakan sebagai berikut, struktur cycle dan struktur culset merupakan dual struktur kebebasan.