Daftar Isi:
Definisi - Apa yang dimaksud dengan Bipartite Graph?
Grafik bipartit adalah grafik di mana satu set simpul grafik dapat dibagi menjadi dua set independen, dan tidak ada dua simpul grafik dalam set yang sama berdekatan. Dengan kata lain, grafik bipartit dapat dianggap sama dengan dua grafik yang berwarna. Grafik bipartit sebagian besar digunakan dalam hubungan pemodelan, terutama antara dua seluruh kelas objek yang terpisah.
Grafik bipartit juga dikenal sebagai bigraph.
Techopedia menjelaskan Grafik Bipartit
Grafik bipartit memiliki dua set simpul, misalnya A dan B, dengan kemungkinan bahwa ketika sebuah tepi ditarik, koneksi harus dapat menghubungkan antara setiap simpul dalam A ke sembarang simpul dalam B. Jika grafik tidak mengandung siklus aneh (jumlah simpul dalam grafik adalah aneh), maka spektrumnya simetris. Angka kromatik, yang merupakan jumlah minimum warna yang diperlukan untuk mewarnai simpul tanpa simpul yang berdekatan berbagi warna yang sama, harus kurang dari atau sama dengan dua dalam kasus grafik bipartit. Semua jenis grafik asiklik (grafik yang tidak memiliki siklus grafik), adalah contoh grafik bipartit. Grafik siklik dianggap bipartit jika semua siklus yang terlibat memiliki panjang genap. Menurut teorema garis pewarnaan Koning, semua grafik bipartit adalah grafik kelas 1.
Grafik bipartit banyak digunakan dalam teori pengkodean modern selain digunakan dalam hubungan pemodelan.
