Pelajari tentang matriks cut-set dasar dalam teori graf: definisi, konstruksi langkah demi langkah, aturan orientasi, dan contoh dengan solusi.
Ketika kita berbicara tentang matriks pemotongan dalam teori graf, umumnya kita berbicara tentang matriks pemotongan fundamental. Pemotongan adalah himpunan minimum cabang-cabang dari graf terhubung sedemikian rupa sehingga ketika cabang-cabang ini dihapus dari graf, maka graf tersebut terpisah menjadi 2 bagian yang disebut sub-graf dan matriks pemotongan adalah matriks yang diperoleh dengan mengambil satu pemotongan pada satu waktu secara baris. Matriks pemotongan dinotasikan dengan simbol [Qf].

Dua sub-graf diperoleh dari graf dengan memilih pemotongan yang terdiri dari cabang [1, 2, 5, 6].
Dengan kata lain, kita dapat mengatakan bahwa pemotongan fundamental dari graf tertentu dengan referensi ke pohon adalah pemotongan yang dibentuk dengan satu ranting dan tautan sisanya. Ranting adalah cabang-cabang pohon dan tautan adalah cabang-cabang co-pohon.
Jadi, jumlah pemotongan sama dengan jumlah ranting.
[Jumlah ranting = N – 1]
Di mana, N adalah jumlah node dari graf atau pohon yang diberikan.
Orientasi pemotongan sama dengan orientasi ranting dan dianggap positif.
Ada beberapa langkah yang harus diikuti saat menggambar matriks pemotongan. Langkah-langkahnya adalah sebagai berikut-
Gambar graf dari jaringan atau sirkuit (jika diberikan).
Kemudian gambar pohonnya. Cabang-cabang pohon akan menjadi ranting.
Kemudian gambar cabang-cabang sisa graf dengan garis putus-putus. Cabang-cabang ini akan menjadi tautan.
Setiap cabang atau ranting pohon akan membentuk pemotongan independen.
Tulis matriks dengan baris sebagai pemotongan dan kolom sebagai cabang.
| Cabang ⇒ | 1 | 2 | 3 | . | . | b | |
| Pemotongan | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = jumlah pemotongan.
b = jumlah cabang.
Qij = 1; jika cabang J ada dalam pemotongan dengan orientasi yang sama dengan cabang pohon.
Qij = -1; jika cabang J ada dalam pemotongan dengan orientasi yang berlawanan dengan cabang pohon.
Qij = 0; jika cabang J tidak ada dalam pemotongan.
Contoh 1
Gambar matriks pemotongan untuk graf berikut.
Jawaban:
Langkah 1: Gambar pohon untuk graf berikut.
Langkah 2: Identifikasi pemotongan. Pemotongan akan menjadi simpul yang hanya memiliki satu ranting dan sejumlah tautan.
Di sini C2, C3 dan C4 adalah pemotongan.
Langkah 3: Gambar matriks.
| Cabang ⇒ | 1 | 2 | 3 | 4 | 5 | 6 | |
| Pemotongan | |||||||
| C2 | +1 | +1 | |||||