Berapa jumlah maksimum dan jumlah minimum simpul p...

Question

Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berderajat ≥ 3?

Kevin L · Accepted Answer

Penjelasan:
Pertanyaan:
Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda?
Solusi:
Jumlah maksimum simpul
Pada graf sederhana, setiap simpul terhubung dengan simpul lain paling banyak sebanyak n-1 simpul, dengan n adalah jumlah simpul pada graf. Hal ini dapat dinyatakan dengan rumus:
d_max ≤ n - 1

di mana d_max adalah derajat maksimum simpul pada graf.
Pada soal, diketahui bahwa derajat minimum simpul adalah 3. Maka, d_max ≥ 3.
Dengan demikian, n ≤ d_max + 1 ≤ 4.
Jumlah minimum simpul
Pada graf sederhana, jumlah sisi minimal sama dengan setengah dari jumlah derajat seluruh simpul. Hal ini dapat dinyatakan dengan rumus:
e ≥ n(d_min)/2

di mana e adalah jumlah sisi pada graf.
Pada soal, diketahui bahwa jumlah sisi adalah 12 dan derajat minimum simpul adalah 3. Maka, 12 ≥ n(3)/2.
Dengan demikian, n ≥ 8.
Kesimpulan
Jumlah maksimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda adalah 4.
Jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda adalah 8.
Penjelasan tambahan
Pada graf sederhana, setiap simpul tidak boleh terhubung dengan dirinya sendiri. Hal ini berarti bahwa matriks ketetanggaan graf sederhana harus berupa matriks diagonal nol.
Dengan menggunakan rumus-rumus yang telah disebutkan di atas, dapat disimpulkan bahwa graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda hanya mungkin memiliki 4 atau 8 simpul.
Kesimpulan
Jumlah maksimum dan minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda adalah 4 dan 8.

Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berderajat ≥ 3?

Mau pemahaman lebih dalam untuk soal ini?

Pertanyaan serupa