Rangkaian dalam Teori Graf (5.1.1 & 5.1.2)

Antara yang berikut, yang manakah BUKAN satu rangkaian?

• Jalan raya yang menyambungkan rumah.

• Jaringan makanan.

• Struktur keluarga Syafiqah.

• Pensil di dalam kotak pensil.

Tatatanda graf merupakan set pasangan tertib iaitu G = (V, E) dengan keadaan;

• V ialah set bintik atau bucu.

• V ialah set tepi atau garis yang menghubungkan sepasang bucu.

• E ialah set tepi atau garis yang menghubungkan sepasang bucu.

• E ialah set bintik atau bucu.

Graf mudah ialah graf yang tidak mengandungi gelung atau berbilang tepi.

Antara yang berikut, yang manakah menunjukkan graf mudah?

• 
• 
• 
• 

Jumlah darjah bagi suatu graf ialah

• dua kali bilangan bucu.

• setengah daripada bilangan bucu.

• dua kali bilangan tepi.

• setengah daripada bilangan tepi.

Nyatakan bilangan bucu, tepi dan darjah bagi graf mudah berikut:

• Bucu = 6

  Tepi = 9

  Darjah = 18

• Bucu = 7

  Tepi = 9

  Darjah = 8

• Bucu = 7

  Tepi = 14

  Darjah = 28

• Bucu = 7

  Tepi = 9

  Darjah = 18

Diberi tiga graf mudah. Graf manakah menunjukkan maklumat berikut?

n(V) = 8

n(E) = 8

bilangan darjah = 16

• 
• 
• 

Diberi graf berbilang tepi dan yang mempunyai gelung. Tentukan set pasangan bucu dan jumlah tepi bagi graf tersebut.

• E = { (P,U), (U,T), (P,Q), (P,O), (Q,R), (Q,O), (R,R), (R,S), (R,O), (S,O), (S,T), (T,O), (U,O) }

  
  

  n(E) = 13

• E = { (P,U), (P,U), (U,T), (U,T), (P,Q), (P,O), (Q,R), (Q,R), (Q,O), (R,R), (R,S), (R,S), (R,O), (S,O), (S,T), (T,O), (U,O) }

  
  

  n(E) = 17

Antara berikut, yang manakah menunjukkan GRAF TAK TERARAH?

• 
• 
• 
• 

Antara yang berikut, yang manakah menunjukkan GRAF BERPEMBERAT ?

• 
• 
• 
• 

Rangkaian di atas menunjukkan 6 kawasan sekolah yang disambungkan antara satu sama lain. Masa perjalanan yang diambil, dalam minit, diwakilkan oleh niai pada tepi.

Cari laluan perjalanan yang mempunyai masa TERPANJANG jika Encik Amir ingin pergi ke kawasan D dari A.

• A $\rightarrow$ C $\rightarrow$ D

• A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D

• A $\rightarrow$ C $\rightarrow$ F $\rightarrow$ E $\rightarrow$ D

• A $\rightarrow$ C $\rightarrow$ E $\rightarrow$ D