tajuk 4 graf
DESCRIPTION
readTRANSCRIPT
MTE 3104 MATEMATIK KEPUTUSAN
TAJUK 4 GRAF
4.1 SINOPSIS
Teori graf mula dijumpai lebih dua ratus tahun dahulu, yang lebih
kepada permainan untuk ahli-ahli matematik dan diambil secara serius
sehinggalah abad ke 20. Perkembangan kuasa komputer
bagaimanapun memberi kesedaran bahawa teori graf boleh
diaplikasikan secara meluas dalam bidang pengurusan perdagangan
dan industri bagi kepentingan ekonomi.
Topik ini akan membincangkan definisi dan jenis-jenis graf.
4.2 HASIL PEMBELAJARAN
1. Mentakrif graf dan terma yang berkaitan dengan graf seperti bucu,
sisi dan darjah.
2. Menjelaskan ciri-ciri pelbagai jenis graf.
3. Menentukan matriks insiden bagi graf yang diberikan.
4.3 KERANGKA TAJUK
31
Graf
Definisi
sisi(edges), bucu(vertex), darjah
(degree)
Jenis-jenis graf
graf ringkas, walk, trail, path, kitar (cycle), digraph, incidence
matrix, graf planar, graf bipartite
MTE 3104 MATEMATIK KEPUTUSAN
4.4 Definisi
Perkataan "graf" (sekurang-kurangnya) mengandungi dua makna
dalam matematik.
i) Dalam matematik asas, "graf" merujuk kepada graf fungsi atau
"graf bagi fungsi," iaitu plot.
ii) Dalam istilah ahli matematik, graf adalah koleksi titik-titik dan garis-
garis yang menyambungkan beberapa subset (mungkin sifar).
Graf juga boleh didefinisikan sebagai set titik-titik dan set sisi-sisi
( garis lurus atau melengkung (arcs)). Setiap sisi disambungkan
kepada satu bucu (titik) yang lain atau bermula dan berakhir pada
bucu yang sama.
Graf adalah terdiri daripada titik-titik yang disambungkan atau tidak
disambungkan oleh garisan.
"dot" dipanggil bucu /mercu(vertex).
Apabila terdapat lebih daripada satu bucu, mereka dipanggil ‘vertices.
"edge" dipanggil sisi atau garis. (atau edges)
Bucu (V) atau nod
• Titik-titik pada graf sering dikenali sebagai bucu graf, tetapi boleh
juga dipanggil "nod" atau hanya "titik."
Sisi/ Sempadan (E) atau lengkuk (arc)
• Garisan yang menyambungkan bucu-bucu pada graf dikenali sebagai
sisi graf, tetapi boleh juga dipanggil "lengkuk" atau "garis”.
32
MTE 3104 MATEMATIK KEPUTUSAN
Darjah bagi bucu dalam sebuah graf.
Darjah atau valensi bagi bucu pada suatu graf adalah bilangan sisi-
sisi yang menyentuh / insiden kepada bucu (garis atau sisi yang
bermula dan berakhir pada bucu atau titik yang sama mempunyai
darjah 2).
Sebagai contoh, darjah bagi bucu-bucu pada graf berikut adalah:
• Formula umum untuk Jumlah darjah = 2n di mana n = bilangan sisi.
Contoh –contoh graf
33
4
MTE 3104 MATEMATIK KEPUTUSAN
Teori graf
• Kajian mengenai graf dikenali sebagai teori graf
. Dalam Teori Graf, graf adalah kumpulan yang mungkin atau tidak mungkin
disambungkan antara satu sama lain oleh garis-garis.
Contoh:
Rajah 4.1: GrafGraf dengan V=abcd dan E=abacbc .
4.5 Jenis – jenis graf.
(1) Graf ringkas (simple graf)
- Suatu graf adalah ringkas jika hanya ada satu sisi disambung
kepada dua nod/titik.
- Tiada lingkaran pada graf ringkas. i.e. tiada sisi-sisi dengan bucu
yang sama pada setiap hujung , dan tidak lebih dari satu sisi
disambung kepada sebarang pasangan bucu.
34
MTE 3104 MATEMATIK KEPUTUSAN
(2) Graf bersambung (Connected graph)
Graf di mana setiap bucu disambungkan (dengan satu sisi atau
lebih satu sisi) antara satu sama lain.
(3) Graf Sempurna (Complete graph)
• Graf di mana setiap bucu disambung pada tiap-tiap bucu
oleh satu garis tunggal.
• Graf sempurna dengan n bucu dipanggil sebagai Kn.
K3 – mempunyai tiga bucu dan tiga sisi.
K4 – mempunyai empat bucu dan enam sisi.
(4) Jalan(Walk), Jejak (trail), Laluan(path), kitaran (cycle)
Jalan (Walk)
• Jalan adalah jujukan yang berselangseli antara bucu dan sisi, bermula dan berakhir dengan bucu.
• Bucu kedua setiap sisi (kecuali sisi terakhir) merupakan bucu pertama bagi sisi yang berikut.
35
MTE 3104 MATEMATIK KEPUTUSAN
Jejak (Trail)
Jejak adalah jalan di mana semua sisi adalah berbeza (jalan di mana
tiada sisi berulang) ie tidak boleh lebih satu sisi menyambungkan dua
bucu.
Laluan (Path)
Laluan adalah jejak di mana tiada bucu berulang.
Kitaran (Cycle)
Kitaran adalah laluan tertutup (laluan yang bermula dan berakhir pada
bucu yang sama).
Contoh
(i) CD, DA, AB, BD, DA adalah walk(jalan (dipanggil juga jalan dari C
ke A).
(ii) CD, DA, AB, BD, DA bukan jejak (trail) kerana DA berulang dua kali
tetapi CD, DA, AB, BC dan CA adalah trail dari C ke A.
(iii) Trail dari C ke A bukan laluan (path) kerana A dan C bertemu dua
kali.
(iv) CD, DA, AB adalah laluan dari C ke B.
36
A B
C D
MTE 3104 MATEMATIK KEPUTUSAN
(5) Laluan Hamiltonian (Hamiltonian Path) , Kitaran Hamiltonian (Hamiltonian Cycle).
Laluan Hamiltonan dalam graf adalah satu jalan yang melalui setiap
bucu graf hanya sekali. Bagaimanapun Laluan Hamiltonain tidak
semestinya melalui semua sisi(edge) graf.
Laluan Hamiltonan yang berakhir di tempat yang sama di mana ia
bermula dipanggil litar Hamiltonan atau kitaran hamiltonain.
Satu kitaran Hamiltonian, litar Hamiltonian, lawatan bucu (vertex tour) atau
kitaran graf adalah kitaran yang bertemu setiap bucu hanya sekali (kecuali
bucu yang bermula dan berakhir di tempat yang sama,dan begitu juga
bertemu dua kali).
Graf yang mengandungi laluan Hamiltonian Laluan hamiltonian(hitam) yang dipanggil Graf Hamiltonian. melalui graf (biru)
(6) Graf Berarah (Directed graph)
• Graf di mana sekurang-kurangnya satu sisi mempunyai arah yang
dikaitkan dengannya.
37
MTE 3104 MATEMATIK KEPUTUSAN
(7) Cara mewakilkan graf
(a) matriks adjacent
Dua bucu adalah adjacent jika mereka disambungkan dengan satu sisi.
Dalam graf ini, bucu A adalah adjacent kepada B, C dan D tetapi tidak
adjacent kepada E or F.
Contoh:
Bucu 1 adjacent kepada bucu 2.
· Bucu 2 adjacent kepada bucu 1, bucu 3, dan bucu 4.
· Bucu 3 adjacent kepada bucu 2 dan bucu 4.
· Bucu 4 adjacent kepada bucu 2 dan bucu 3.
38
MTE 3104 MATEMATIK KEPUTUSAN
Catatan : Ada sambungan : 1
Tiada sambungan : O
Maklumat di atas boleh diwakilkan seperti jadual di bawah.
Vertex 1 Vertex 2 Vertex 3 Vertex 4
Vertex 1 0 1 0 0
Vertex 2 1 0 1 1
Vertex 3 0 1 0 1
Vertex 4 0 1 1 0
(b) Matriks incidence
• Graf yang diwakilkan oleh suatu matriks E (edges) dan V (vertices)
dimana [edge, vertex] mengandungi data sisi.
• Suatu sisi yang disambung dengan dua bucu , bucu-bucu ini dipanggil
‘incident’ kepada sisi tersebut, atau sisi ‘incident’ kepada 2 bucu.
• Bucu 1 incident dengan sisi 'a.'
• Bucu 2 incident dengan sisi 'a,' sisi 'b,' dan sisi 'd.'
• Bucu 3 incident dengan sisi 'b,' dan sisi 'c.'
• Bucu 4 incident dengan 'c,' dan sisi 'd.'
39
MTE 3104 MATEMATIK KEPUTUSAN
• Maklumat di atas boleh diwakilkan seperti jadual di bawah.
Side
'a''
Side
'b' '
Side
'c'
Side
'd'
Vertex 1 1 0 0 0Vertex 2 1 1 0 1Vertex 3 0 1 1 0Vertex 4 0 0 1 1
(7) Graf planar
Graf planar (satah) adalah graf yang boleh dilukis pada satah
(Euclid) tanpa berlaku persilangan sisi.
Graf yang tidak boleh dilukis pada satah tanpa tepi bersilang sisi
dipanggil graf non planar.
(8) Graf biparttite
Graf biparttite adalah graf khas di mana set bucu-bucu boleh
dibahagikan kepada dua set bucu U dan V di mana tiada dua nod
pada set yang sama disambungkan dengan sesuatu sisi.
40
MTE 3104 MATEMATIK KEPUTUSAN
Contoh:
(i)
graf asal bipartite 1 bipartie 2
(ii)
(9) Graf isomorphic
Dua graf adalah isomorphic jika mereka mempunyai bilangan bucu
sepada yang sama dan darjah sepadan yang sama.
Contoh : Kedua-dua graf adalah isomorphic
(i)
41
MTE 3104 MATEMATIK KEPUTUSAN
(ii)
(10) Tree (Pokok)
Suatu pokok adalah graf ringkas bersambung yang tidak
mempunyai kitaran atau lingkaran (cycle atau loop).
Pokok Bukan pokok
42
MTE 3104 MATEMATIK KEPUTUSAN
Latihan:
1. Lukiskan graf dengan empat bucu di mana satu bucu mempunyai darjah 4,
satu bucu dengan darjah 2 dan dua bucu dengan darjah 1.
2. Jadual berikut menunjukkan bilangan bucu dengan darjah (order) 1, 2 dan
3 dalam tiga jenis graf. Lukis satu contoh bagi setiap graf ini.
Darjah bagi bucu
1 2 3
Graf 1
Graf 2
Graf 3
3
2
1
0
2
1
1
0
1
3. Tuliskan graf berikut dalam bentuk matriks adjacency/ matriks incidence.
(i) (ii)
4. (i) Berikan dua sifat yang menjadikan sesuatu graf itu dikenali sebagai
pokok.
(ii) Lukis tiga pokok yang berbeza yang mengandungi setiap satunya
lima bucu dan empat sisi.
43
MTE 3104 MATEMATIK KEPUTUSAN
5. Lukiskan graf yang sepadan dengan matriks adjacency berikut.
A B C D A B C D
(a) (0 11 110 0 110 0 011 0 0
) (b) (01 2 010 0 120 0 001 0 2
)
Buku rujukan
Parramore, K., et. al. (2004). Decision Mathematics 1. 3rd ed. U.K. Hodder
Murray.
Parramore, K., et. al. (2004). Decision Mathematics 2 and C . 3rd ed. U.K.
Hodder Murray.
Brian, J, (2005). Decision Mathematics , U.K. Oxford University Press.
44