Unit 1 — Membaca Argumen sebagai Jejaring Klaim

Merekonstruksi langkah yang hilang dan menguji batas pengetahuan

Unit praktik untuk membaca klaim, asumsi, pembuktian, dan bukti empiris secara terpisah serta dapat ditelusuri.

1 Hasil belajar

Setelah menyelesaikan unit ini, Anda mampu:

1. membedakan definisi, asumsi, klaim, ilustrasi, dan kesimpulan dalam teks matematika;
2. mengubah frasa seperti jelas atau mengikuti argumen pertukaran menjadi kewajiban pembuktian yang eksplisit;
3. merekonstruksi langkah yang dihilangkan tanpa memperkuat klaim secara tidak sah;
4. menguji peranan asumsi menggunakan contoh dan contoh tandingan;
5. menggunakan komputasi sebagai bukti empiris diagnostik, bukan sebagai pengganti pembuktian; dan
6. mencatat sumber, keputusan interpretatif, serta ketidakpastian dalam memo pembacaan yang dapat diaudit.

CatatanPrasyarat

Unit ini mengandaikan bahwa Anda sudah mengenal graf berhingga, lintasan, siklus, pohon, pembuktian kontradiksi, dan cara menjalankan skrip Python yang sudah tersedia. Sintaks Python dan algoritme pohon merentang minimum bukan materi unit ini.

2 Membaca bukan sekadar bergerak dari kiri ke kanan

Teks penelitian matematika sering memadatkan penalaran. Penulis dapat melewati langkah yang dianggap baku, menggunakan definisi dari bagian terdahulu, atau menyatakan bahwa hasil “langsung mengikuti” suatu teknik. Pembaca harus menentukan bukan hanya arti setiap kalimat, tetapi juga:

• apa tepatnya yang diklaim;
• dengan asumsi apa klaim itu berlaku;
• hasil sebelumnya mana yang benar-benar dipakai;
• langkah mana yang belum dibuktikan; dan
• jenis dukungan apa yang diberikan untuk setiap kesimpulan.

Gunakan lima label berikut dalam catatan pembacaan.

Label	Peran	Pertanyaan pemeriksa
D	definisi	Objek apa yang sedang ditentukan maknanya?
A	asumsi	Syarat apa yang boleh digunakan?
K	klaim	Pernyataan apa yang harus dibuktikan?
J	justifikasi	Alasan apa yang benar-benar diberikan?
T	tugas terbuka	Kewajiban pembuktian apa yang masih hilang?

Label ini bukan tata cara wajib. Fungsinya ialah membuat struktur epistemik sebuah teks terlihat dan dapat diperiksa orang lain.

3 Petikan sintetis

Petikan berikut ditulis khusus untuk unit ini; petikan ini bukan kutipan atau terjemahan dari sumber lain.

Misalkan $G=(V,E)$ adalah graf terhubung berhingga dan $w:E\to\mathbb{R}$ memberi bobot berbeda pada setiap sisi. Pohon merentang minimum $G$ bersifat tunggal. Hal ini mengikuti dari argumen pertukaran yang biasa.

Sebelum mencoba membuktikannya, uraikan petikan tersebut.

• D1. Pohon merentang adalah subgraf yang memuat semua simpul, terhubung, dan tidak memiliki siklus.
• D2. Bobot pohon merentang $T$ adalah $$w(T)=\sum_{e\in E(T)}w(e).$$
• D3. Pohon merentang minimum adalah pohon merentang dengan bobot sekecil mungkin.
• A1. Graf berhingga.
• A2. Graf terhubung.
• A3. Bobot semua sisi berbeda.
• K1. Hanya ada satu pohon merentang minimum.
• J1. “Argumen pertukaran yang biasa.”
• T1. Menjelaskan objek yang dipertukarkan.
• T2. Membuktikan bahwa hasil pertukaran masih berupa pohon merentang.
• T3. Membuktikan bahwa pertukaran menghasilkan bobot lebih kecil.
• T4. Menjelaskan letak kontradiksi.

Masalah pembacaan sekarang terukur: kita harus menutup T1–T4.

4 Rekonstruksi pembuktian

Teorema 1 Misalkan $G=(V,E)$ adalah graf terhubung berhingga. Jika setiap dua sisi yang berbeda mempunyai bobot berbeda, maka $G$ mempunyai tepat satu pohon merentang minimum.

Bukti 1. Karena $G$ berhingga dan terhubung, himpunan pohon merentangnya berhingga dan tidak kosong. Jadi setidaknya ada satu pohon merentang minimum.

Andaikan terdapat dua pohon merentang minimum berbeda, $T$ dan $T'$. Selisih simetris $E(T)\mathbin{\triangle}E(T')$ tidak kosong. Pilih sisi $e$ dengan bobot paling kecil di antara seluruh sisi dalam selisih simetris itu. Setelah menukar nama $T$ dan $T'$ jika perlu, anggap $e\in E(T)\setminus E(T')$.

Tambahkan $e$ kepada $T'$. Kedua ujung $e$ sebelumnya dihubungkan oleh tepat satu lintasan dalam $T'$, sehingga penambahan $e$ menghasilkan tepat satu siklus $C$.

Siklus $C$ memuat suatu sisi $f\in E(T')\setminus E(T)$. Jika semua sisi $C\setminus\{e\}$ juga berada dalam $T$, sisi-sisi tersebut bersama $e$ akan membentuk siklus dalam $T$. Hal itu mustahil karena $T$ adalah pohon.

Sisi $f$ berada dalam selisih simetris. Karena $e$ dipilih sebagai sisi berbobot paling kecil di seluruh selisih simetris dan semua bobot berbeda, $w(e)<w(f)$.

Hapus $f$ dari siklus dan pertahankan $e$. Graf $$T''=T'-f+e$$ tetap memuat semua simpul, terhubung, dan tidak memiliki siklus; jadi $T''$ adalah pohon merentang. Namun, $$w(T'')=w(T')-w(f)+w(e)<w(T'),$$ bertentangan dengan keminimuman $T'$. Jadi dua pohon merentang minimum berbeda tidak mungkin ada. Pohon merentang minimum tersebut tunggal.

Langkah kuncinya bukan aljabar terakhir, melainkan menemukan $f$ dan membuktikan $f\notin T$. Itulah isi yang disembunyikan frasa “argumen pertukaran yang biasa.”

5 Mengaudit asumsi

Asumsi “semua bobot berbeda” cukup untuk menjamin ketunggalan, tetapi tidak diperlukan.

TipContoh: bobot berulang tetapi solusi tunggal

Pada segitiga dengan bobot sisi $1,1,2$, pohon yang memakai kedua sisi berbobot $1$ adalah satu-satunya pohon merentang minimum.

PeringatanContoh tandingan terhadap ketunggalan tanpa syarat

Pada segitiga dengan ketiga sisi berbobot $1$, setiap pilihan dua sisi menghasilkan pohon merentang berbobot $2$. Ada tiga pohon merentang minimum.

Keterhubungan juga bukan hiasan. Graf tak terhubung tidak mempunyai pohon merentang menurut definisi di atas. Untuk graf seperti itu, objek yang sesuai adalah hutan merentang minimum—sebuah klaim berbeda.

6 Eksperimen dan pembuktian mempunyai pekerjaan berbeda

Skrip verify_mst_uniqueness.py memeriksa semua $6!=720$ penetapan bobot berbeda $1,\ldots,6$ pada enam sisi $K_4$. Skrip juga menghitung pohon merentang minimum pada segitiga berbobot sama. Ia mengenumerasi pohon merentang secara langsung dan tidak memakai algoritme MST sebagai kotak hitam, sehingga pemeriksaannya tidak bergantung secara melingkar pada argumen yang sedang dikaji.

Keluaran yang diharapkan adalah:

k4_distinct_weight_assignments_checked: 720
k4_uniqueness_violations: 0
equal_weight_triangle_mst_count: 3

Eksperimen ini dapat menemukan contoh tandingan, mengungkap salah baca definisi, dan menghasilkan contoh konkret untuk membimbing pembuktian. Ia tidak membuktikan teorema: pemeriksaan hanya mencakup satu graf dan kasus berhingga, serta tetap bergantung pada kebenaran implementasi.

PentingBatas inferensi

“Program tidak menemukan pelanggaran” dan “teorema telah dibuktikan” adalah dua klaim berbeda. Memo penelitian harus menyatakan yang pertama tanpa diam-diam mengubahnya menjadi yang kedua.

7 Praktik terpandu

Baca kembali kalimat berikut:

Siklus $C$ memuat suatu sisi $f\in E(T')\setminus E(T)$.

Jawab secara berurutan:

1. Mengapa $C$ muncul setelah $e$ ditambahkan pada $T'$?
2. Apa akibatnya jika semua sisi $C\setminus\{e\}$ berada dalam $T$?
3. Sifat pohon mana yang akan dilanggar?
4. Mengapa $f$ berada dalam selisih simetris?
5. Mengapa diperoleh $w(e)<w(f)$, bukan hanya $w(e)\leq w(f)$?

CatatanPembahasan

Dalam pohon terdapat tepat satu lintasan antara dua simpul. Sisi baru $e$ menutup lintasan itu menjadi siklus. Jika seluruh lintasan tersebut juga berada dalam $T$, lintasan itu bersama $e$ menjadi siklus dalam $T$. Karena $f\in T'$ tetapi $f\notin T$, sisi itu berada dalam selisih simetris. Ketaksamaan menjadi tegas karena bobot semua sisi berbeda.

8 Latihan

1. O017-U01-X01. Tandai D, A, K, J, dan T pada petikan sintetis.
2. O017-U01-X02. Tulis ulang argumen dengan memilih sisi teringan hanya dalam $T\setminus T'$. Tentukan apakah argumen masih sah.
3. O017-U01-X03. Berikan graf dengan bobot yang tidak semuanya berbeda tetapi mempunyai pohon merentang minimum tunggal.
4. O017-U01-X04. Berikan contoh yang menunjukkan bahwa menghapus asumsi keterhubungan membuat pernyataan asli salah sasaran.
5. O017-U01-X05. Seorang pembaca menulis, “Program memeriksa semua penetapan bobot berbeda pada $K_4$, jadi teorema terbukti.” Identifikasi dua kesalahan epistemiknya.
6. O017-U01-X06. Tulis memo pembacaan paling banyak 400 kata yang memuat identitas klaim, definisi, satu langkah yang semula hilang, hasil rekonstruksi, satu pengujian komputasional, batas pengujian, dan sumber yang dirujuk.

9 Petunjuk dan panduan jawaban

1. O017-U01-H01. Pohon merentang dan bobot pohon adalah definisi; keberhinggaan, keterhubungan, dan bobot berbeda adalah asumsi; ketunggalan adalah klaim; argumen pertukaran adalah justifikasi yang belum lengkap.
2. O017-U01-H02. Belum tentu sah: sisi teringan dalam $T\setminus T'$ belum tentu lebih ringan daripada $f\in T'\setminus T$. Minimum pada seluruh selisih simetris memberi perbandingan yang diperlukan.
3. O017-U01-H03. Gunakan segitiga berbobot $1,1,2$.
4. O017-U01-H04. Dua simpul tanpa sisi di antaranya sudah cukup; graf itu tidak mempunyai pohon merentang.
5. O017-U01-H05. Pemeriksaan hanya mencakup satu graf dan kasus berhingga; keluarannya juga bergantung pada implementasi.
6. O017-U01-H06. Memo dinilai dari keterlacakan setiap klaim, bukan dari panjang atau gaya bahasa.

10 Tugas penyelesaian unit

Serahkan satu memo rekonstruksi yang memenuhi Latihan 6 dan lampirkan keluaran komputasi. Memo lulus jika:

• klaim dan asumsi dinyatakan lengkap;
• semua kewajiban pembuktian utama ditutup;
• eksperimen dipisahkan secara eksplisit dari pembuktian;
• satu batas atau contoh tandingan dianalisis; dan
• asal setiap teks, data, serta kode dapat ditelusuri.

11 Provenance dan bacaan lanjutan

Petikan sintetis, eksposisi, pembuktian, latihan, panduan jawaban, dan kode adalah materi asli O017. Teorema ketunggalan MST untuk bobot sisi berbeda adalah hasil klasik; presentasi ini tidak menyalin redaksi sumber tertentu. Artikel Kruskal merupakan rujukan sejarah algoritme pohon merentang minimum (Kruskal 1956), bukan klaim bahwa redaksi pembuktian di atas berasal darinya.

Untuk praktik reproduksibilitas dan rekayasa artefak penelitian yang lebih luas, lihat The Turing Way (The Turing Way Community 2025) dan Research Software Engineering with Python (Irving dkk. 2021). Modul yang diadaptasi dari kedua karya itu baru akan masuk pada unit selanjutnya setelah identitas berkas dan hak komponennya dibekukan.

Daftar Pustaka

Irving, Damien, Kate Hertweck, Luke Johnston, Joel Ostblom, Charlotte Wickham, dan Greg Wilson. 2021. Research Software Engineering with Python: Building Software that Makes Research Possible. Chapman & Hall/CRC Press. https://third-bit.com/py-rse/.

Kruskal, Joseph B. 1956. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7 (1): 48–50. https://doi.org/10.1090/S0002-9939-1956-0078686-7.

The Turing Way Community. 2025. The Turing Way Handbook for Reproducible, Ethical and Collaborative Research. Versi 1.2.3. https://doi.org/10.5281/zenodo.3233853.