tajuk 4 graf

17
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

Upload: jia-ren

Post on 04-Jan-2016

445 views

Category:

Documents


10 download

DESCRIPTION

read

TRANSCRIPT

Page 1: Tajuk 4 Graf

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

Page 2: Tajuk 4 Graf

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

Page 3: Tajuk 4 Graf

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

Page 4: Tajuk 4 Graf

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

Page 5: Tajuk 4 Graf

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

Page 6: Tajuk 4 Graf

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

Page 7: Tajuk 4 Graf

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

Page 8: Tajuk 4 Graf

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

Page 9: Tajuk 4 Graf

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

Page 10: Tajuk 4 Graf

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

Page 11: Tajuk 4 Graf

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

Page 12: Tajuk 4 Graf

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

Page 13: Tajuk 4 Graf

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

Page 14: Tajuk 4 Graf

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