* The preview only shows a few pages of manuals at random. You can get the complete content by filling out the form below.
Description
POWER NOW
GRAPH PART 1 JUNAIDI,M.PD & Dr. Amrullah M.Sc
L/O/G/O www.themegallery.com
Tujuan pembelajaran 1
• Mengetahui terminologi dalam graf • Mengetahui definisi dalam graf
2
• Mengetahui proposisi dalam graf • Menganalisa graf tertentu
3
• Problem solving terkait graf • Pembuktian graf
www.themegallery.com
Pengenalan simbol
A
k
Himpunan dari semua Subset A dengan k elemen Himpunan dengan k elemen disebut k-set Subset-subset dengan k elemen disebut k-subset
www.themegallery.com
𝐴 = 𝑎, 𝑏, 𝑐 Sub set dari A ? Sub set dari A dengan elemen sebanyak 3? Sub set dari A dengan elemen sebanyak 2? Sub set dari A dengan elemen sebanyak 1?
www.themegallery.com
Dalam graf Kita akan mengenal simpul (vertex/nodes) dilambangkan dengan V
∙ Dalam graf Kita akan mengenal sisi (Edge) dilambangkan dengan E
www.themegallery.com
Definisi 1.1 Graph/graf Pasangan G=(V,E) adalah himpunan-himpunan sedemikian sehingga E subset dari 𝑉 2 . – Elemen dari V adalah simpul-simpul pada grap. – V boleh tidak boleh ∅ – Elemen dari E adalah sisi pada grap.
www.themegallery.com
Diberikan V = {1, 2, 3, 4} dan E = {{1, 5}, {2, 3}}.
Apakah G(V, E) suatu graf ??? Jelaskan
Bagaimana supaya jadi graf ?
www.themegallery.com
Diberikan V = {1, 2, 3, 4} dan E = {{1, 2}, {2, 3}}.
Apakah G=(V, E) suatu graf ??? Jelaskan
www.themegallery.com
Diberikan V = {1} dapatkah anda menemukan/ membuat sisi E ? Apakah G=(V, E) suatu graf ??? Jelaskan
Apakah yang dapat anda simpulkan ?
Berikan nama khusus graf ini
www.themegallery.com
Diberikan V = {a, b, c, d} dan E = {{a, b}, {b, c}}. Apakah G(V, E) suatu graf ??? Jelaskan
Apakah kesimpulan anda dari graf ini jika dibandingkan dengan graf sebelumnya ?
www.themegallery.com
Diberikan V = {1, 2, 3, 4} dan E = {{1, 2}, {2, 3}}. Dapatkah anda menggambarkan graf diatas ? Gambar yang anda peroleh kita sebut dengan geometri dari G=(V,E) atau representasi graf G=(V,E)
www.themegallery.com
www.themegallery.com
e
a b c
d
Dapatkah anda menyatakan graf diatas dengan G=(V,E)
www.themegallery.com
𝒆𝟏
e
𝒆𝟑
a
𝒆𝟐
𝒆𝟒
b
𝒆𝟓
c
d
Pada graf diatas 𝒆𝟏 dan 𝒆𝟐 menghubungkan dua simpul yang sama, sehingga graf diatas dikatakan memiliki sisi ganda atau multi edges
www.themegallery.com
𝒆𝟏
e
𝒆𝟑
a
𝒆𝟐
𝒆𝟔
𝒆𝟒
b
𝒆𝟓
c
d
Pada graf diatas 𝒆𝟔 menghubungkan satu simpul yang sama, sehingga graf diatas dikatakan memiliki sisi gelang
www.themegallery.com
Definisi 1.2 Suatu graf yang tidak memiliki gelang dan sisi ganda disebut graf sederhana Suatu graf yang memiliki sisi ganda disebut graf ganda , Sedangkan graf yang memiliki gelang disebut graf semu.
www.themegallery.com
Graf sederhana, karena tidak ada sisi ganda dan gelang
www.themegallery.com
Graf ganda, karena ada sisi ganda
www.themegallery.com
Graf semu, karena ada sisi gelang
www.themegallery.com
Insidensi dan derajat Definisi1.3:
Dua simpul u,v dari G dikatakan berdekatan/bertetangga jika uv adalah sisi pada G. Definisi1.4: Dua sisi e dan f berdekatan jika memiliki simpul persekutuan. www.themegallery.com
– Jika semua simpul pada G berdekatan berpasangan maka G lengkap. – Grap lengkap dengan n simpul adalah 𝐾𝑛
www.themegallery.com
– 𝐾 3 disebut triangle – Pasangan simpul atau sisi yang tidak berdekatan disebut independen
www.themegallery.com
Dapatkah anda menggambarkan satu graf lengkap ?
www.themegallery.com
e
a b c
d
Dapatkah anda menyatakan pasangan simpul-simpul yang bertetangga/berdekatan ? Dapatkah anda menyatakan pasangan sisi-sisi yang berdekatan ?
www.themegallery.com
Diberikan V = {a, b, c, d} dan E = {{a, b}, {b, c}, {a,d},{c,d}}. Dapatkah anda menyatakan pasangan simpul-simpul yang bertetangga/berdekatan ? Dapatkah anda menyatakan pasangan sisi-sisi yang berdekatan ?
www.themegallery.com
Definisi 1.5 Suatu graf yang setiap simpulnya diberi label disebut graf berlabel
Definisi 1.5
Banyaknya simpul dari graf G disebut order, ditulis |G|; banyaknya sisi dari graf G ditulis ||G|| .
www.themegallery.com
Definisi 1.6 Orde dari graf adalah banyaknya simpul dari graf Ukuran dari graf adalah banyaknya sisi dari graf
Banyaknya simpul dari graf G disebut orde, ditulis |G|; banyaknya sisi dari graf G ditulis ||G|| .
www.themegallery.com
Definisi 1.7
Derajat dari suatu simpul v pada graf adalah banyaknya sisi yang bersisian dengan v, dinotasikan dengan 𝑑(𝑣)
www.themegallery.com
Teorema 1.1
Misalkan graf G dengan q sisi dan n simpul maka 𝑛
𝑑 𝑣𝑖 = 2𝑞 𝑖=1
www.themegallery.com
Teorema 1.2
Banyaknya simpul yang berderajat ganjil dalam graf selalu genap
www.themegallery.com