Rangkaian dalam teori Graf (Nota Ringkas Matematik Tingkatan 4 bab 5 (Rangkaian dalam teori Graf)

Rangkaian dalam teori Graf | Nota Ringkas Matematik Tingkatan 4 bab 5 | Rangkaian dalam teori Graf | My Wislah | Wislah Malaysia |

Dalam bab ini, kita telah membincangkan tentang rangkaian dalam teori graf. Graf digunakan untuk menggambarkan data yang terdiri daripada objek diskret dan menggambarkan hubungan antara objek-objek tersebut secara grafik. Rangkaian adalah sebahagian dari graf yang mempunyai sifat tersendiri terkait dengan bucu dan tepi, dan struktur data rangkaian berkaitan dengan banyak ke banyak. Kami juga membincangkan tentang jenis-jenis graf seperti graf mudah, graf berarah, graf tidak berarah, graf berpemberat dan graf tidak berpemberat. Selain itu, kami juga membincangkan tentang subgraf dan pohon suatu graf.

Rangkaian dalam teori Graf

Rangkaian

Hubungan antara rangkaian dan graf

1. Graf digunakan untuk menggambarkan data yang terdiri daripada objek diskret dan menggambarkan hubungan antara objek-objek tersebut secara grafik.
2. Dalam teori graf, graf diinterpretasikan sebagai serangkaian titik yang saling berhubungan atau tidak saling berhubungan melalui garis.
3. Titik-titik tersebut dikenali sebagai simpul atau bucu, dan garis yang menghubungkan dua bucu disebut tepi.
4. Graf sering digunakan untuk menggambarkan rangkaian.
5. Rangkaian adalah sebahagian dari graf yang mempunyai sifat tersendiri terkait dengan bucu dan tepi, dan struktur data rangkaian berkaitan dengan banyak ke banyak.
6. Notasi graf merupakan himpunan pasangan terurut, yaitu G = (V, E), dengan keadaan:
   • V ialah himpunan titik atau simpul, V = {v1, v2, v3, …, vn}
   • E ialah himpunan tepi atau garis yang menghubungkan sepasang simpul.
   • Derajat, d, adalah bilangan tepi yang menghubungkan sepasang simpul.
7. Bilangan derajat suatu graf adalah dua kali jumlah tepi, yaitu Σ (v) = 2E.

Graf Mudah

1. Graf mudah adalah graf yang tidak mengandungi gelung atau tepi berganda.
2. Bilangan derajat suatu graf adalah dua kali jumlah tepi.
3. Tepi berganda dan gelung pada graf
4. Tepi berganda
5. Melibatkan dua simpul.
6. Tepi berbentuk lengkung atau bulatan yang berbalik kepada simpul asal.
7. Bilangan derajat setiap gelung adalah dua.

Gelung

1. Melibatkan dua simpul.
2. Tepi berbentuk lengkung atau bulatan yang berbalik kepada simpul asal.
3. Bilangan derajat setiap gelung adalah 2.

Perbezaan antara graf berarah dan graf tidak berarah

Graf berarah    

1. Jenis graf yang mempunyai himpunan terurut simpul.
2. Tepi mewakili arah untuk simpul.
3. Mempunyai anak panah yang mewakili tepi.

Graf tidak berarah

1. Jenis graf yang mempunyai himpunan tak terurut simpul.
2. Tepi tidak mewakili arah untuk simpul.
3. Tidak mempunyai anak panah yang mewakili tepi.

Perbezaan antara graf berpemberat dan graf tidak berpemberat

Graf berpemberat         

1. Jenis graf terarah dan tidak terarah.
2. Tepi diberi nilai atau pemberat.

Graf tidak berpemberat

1. Jenis graf terarah dan tidak terarah.
2. Tidak ada nilai atau pemberat yang dinyatakan.

Tepi mewakili:

– Jarak antara dua bandar.

– Masa yang diambil untuk pergerakan.

– Nilai arus litar elektrik.

– Kos.

Tepi menghubungkan maklumat:

– Hierarki jawatan dalam carta organisasi.

– Peta alir.

– Peta pokok.

– Peta buih.

Subgraf

Definisi

1. Subgraf adalah sebahagian atau keseluruhan graf yang dilukis semula tanpa mengubah kedudukan asal simpul dan tepi.
2. Suatu graf H dikatakan sebagai subgraf dari graf G jika,
3. simpul-simpul graf H adalah subset dari simpul-simpul graf G, yaitu V(H) ⊂ V(G)
4. tepi-tepi graf H adalah subset dari tepi-tepi graf G, yaitu E(H) ⊂ E(G)
5. pasangan simpul pada setiap tepi graf H sama dengan tepi pada graf G.

Pohon suatu graf adalah subgraf dari graf tersebut dengan ciri-ciri berikut:

1. Graf mudah, yaitu tanpa gelung atau tepi berganda.
2. Semua simpul saling terhubung dan setiap pasangan simpul terhubung oleh tepi tunggal.
3. Bilangan tepi = bilangan simpul – 1.
4. Bilangan simpul = n.
5. Bilangan tepi = n-1.

Kesimpulan

Dalam teori graf, graf digunakan untuk menggambarkan hubungan antara objek diskret secara grafik. Rangkaian adalah sebahagian dari graf yang mempunyai sifat tersendiri terkait dengan bucu dan tepi, dan struktur data rangkaian berkaitan dengan banyak ke banyak. Jenis-jenis graf termasuk graf mudah, graf berarah, graf tidak berarah, graf berpemberat dan graf tidak berpemberat. Subgraf merupakan sebahagian atau keseluruhan graf yang dilukis semula tanpa mengubah kedudukan asal simpul dan tepi. Pohon suatu graf adalah subgraf dari graf tersebut dengan ciri-ciri khusus. Dalam keseluruhan, teori graf adalah topik penting dalam matematik dan sains komputer yang melibatkan penggunaan graf dalam mewakili data dan hubungan antara objek.