Graf dan jaringan
Diperkenalkan| English | Bahasa Indonesia |
|---|---|
| graph/ɡræf/ | graf |
| vertices/ˈvɜːtɪsiːz/ | titik sudut |
| edges/ˈedʒɪz/ | sisi |
| degree/dɪˈɡriː/ | derajat |
| path/pæθ/ | jalur |
| cycle/ˈsaɪkl/ | siklus |
| connected/kəˈnektɪd/ | terhubung |
| tree/triː/ | pohon |
| weighted graph/ˈweɪtɪd ɡræf/ | graf berbobot |
| shortest path/ˈʃɔːtɪst pæθ/ | jalur terpendek |
Model koneksi memerlukan asumsinya
- Graf memiliki titik dan sisi. Tentukan apa yang mereka wakili dan apakah koneksinya terarah, berbobot, atau tak terarah.
- Lembar kerja menggunakan graf sederhana tak terarah terbatas tanpa loop atau sisi ganda. Posisi gambar tidak mengubah koneksi mereka, tetapi anak panah atau bobot sisi dapat mengubah model matematika.
Hitung koneksi secara konsisten
- Derajat menghitung sisi insiden dalam graf sederhana tak terarah. Derajat total adalah dua kali jumlah sisi, jadi harus genap.
- Jalur mengikuti koneksi; siklus kembali ke titik awalnya tanpa mengulang vertex lain. Graf terhubung ketika setiap vertex dapat dicapai dari setiap vertex lainnya.
Dalam graf tak berarah sederhana tanpa loop, empat tepi bertemu dengan sebuah vertex. Berapa derajatnya?
Derajatnya adalah 4, jumlah tepi insiden di bawah konvensi graf yang stated.
Pohon memerlukan dua sifat
- Pohon terhubung dan tidak memiliki siklus. Pohon terbatas dengan n vertex memiliki n dikurangi 1 sisi.
- Memiliki n dikurangi 1 sisi saja tidak membuktikan pohon: segitiga plus komponen dua-vertex terpisah memiliki lima vertex dan empat sisi tetapi tidak terhubung dan siklik.
Sebuah pohon memiliki 4 titik sudut. Berapa banyak sisinya?
Pohon finite dengan empat vertex memiliki n − 1 = 3 tepi. Perhitungan ini bergantung pada graf tersebut benar-benar terhubung dan akliklik.
Dalam jaringan tak berarah yang terhubung dengan biaya sisi yang positif secara ketat, mengapa subgraf terhubung berbiaya minimum yang mencakup semua simpul tidak memuat siklus?
Menghapus salah satu sisi siklus mempertahankan konektivitas dan menurunkan total biaya karena bobotnya positif secara ketat. Oleh karena itu, subgraf siklik tidak dapat menjadi minimum di bawah asumsi ini.
Jalan penghubung biaya positif. Untuk jaringan terhubung dengan biaya jalan yang ketat positif, menghapus sisi siklus meninggalkan konektivitas dan menurunkan biaya. Subgraf penghubung biaya minimum karena itu adalah pohon. Untuk menemukan pohon merentang minimum, pilih sisi yang menghubungkan semua vertex tanpa siklus; memilih secara buta n dikurangi 1 sisi termurah dapat meninggalkan komponen terpisah.
Rute terpendek bukan pohon merentang
- Graf berbobot melampirkan nilai tertentu ke setiap sisi. Jalur terpendek meminimalkan bobot rute antara endpoint yang diberikan.
- Pohon merentang minimum sebaliknya menghubungkan setiap vertex dengan total bobot termasuk minimum. Rute terpendek dapat memiliki lebih banyak sisi daripada rute langsung mahal; jumlahkan bobot alih-alih menghitung sisinya.
Cocokkan setiap situasi dengan apa yang seharusnya menjadi titik sudut dan sisinya.
Memutuskan apa yang diwakili oleh titik sudut adalah tahap pemodelan, dan di situlah nilai skor berada.
Sisi tertutup mengubah kelayakan. Lembar 4.5 menemukan rute dengan bobot 7, lalu menutup sisi dan memeriksa penggantian dengan bobot 9. Jangan gunakan total lama untuk jalur yang tidak lagi ada.
Dua gambar yang tampak berbeda pasti merupakan graf yang berbeda.
Tata letak yang berbeda dapat memiliki matriks ketetanggaan berlabel yang sama. Bandingkan juga arah dan bobot ketika keduanya merupakan bagian dari graf yang ditentukan.
Bandingkan semua struktur yang relevan dengan pertanyaan: kecocokan simpul, kedekatan, arah, dan bobot jika ditentukan. Gambar yang terlihat sama belum tentu merepresentasikan graf yang sama; tata letak berbeda dapat merepresentasikan koneksi berlabel yang sama.