Download - Konsep Dasar Graf
Outline
Konsep Dasar Teori Graf
Drs. Slamin, M.Comp.Sc.,Ph.D
Program Studi Pendidikan MatematikaUniversitas Jember
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Outline
Outline
1 Pengertian Graf
2 Jalan dan Lintasan
3 Jarak, Diameter dan Girth
4 Subgraf
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Outline
Outline
1 Pengertian Graf
2 Jalan dan Lintasan
3 Jarak, Diameter dan Girth
4 Subgraf
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Outline
Outline
1 Pengertian Graf
2 Jalan dan Lintasan
3 Jarak, Diameter dan Girth
4 Subgraf
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Outline
Outline
1 Pengertian Graf
2 Jalan dan Lintasan
3 Jarak, Diameter dan Girth
4 Subgraf
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Pengertian Graf
Definisi
Sebuah graf tak berarah G biasanya disebut graf sajadidefinisikan sebagai sebuah pasangan himpunan(V (G), E(G)), dimana V (G) adalah himpunan berhingga takkosong dari elemen yang disebut titik, dan E(G) adalahsebuah himpunan (mungkin kosong) dari pasangan tak terurut{u, v} dari titik-titik u, v ∈ V (G) yang disebut sisi.
V (G) disebut himpunan-titik dari G dan E(G) disebuthimpunan-sisi dari G.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Pengertian Graf
Definisi
Sebuah graf tak berarah G biasanya disebut graf sajadidefinisikan sebagai sebuah pasangan himpunan(V (G), E(G)), dimana V (G) adalah himpunan berhingga takkosong dari elemen yang disebut titik, dan E(G) adalahsebuah himpunan (mungkin kosong) dari pasangan tak terurut{u, v} dari titik-titik u, v ∈ V (G) yang disebut sisi.
V (G) disebut himpunan-titik dari G dan E(G) disebuthimpunan-sisi dari G.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Pengertian Graf (lanjutan)
Contoh
Graf dengan himpunan-titik V = {v1, v2, v3, v4, v5, v6, v7} danhimpunan-sisi E = {v1v4, v4v3, v3v5, v5v4, v4v7}.
v7v4v1
v2 v6
v5v3
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Pengertian Graf (lanjutan)
Sebuah graf G mungkin mengandung loop, yaitu, sisi yangberbentuk {u, u}, dan/atau multi-sisi, yaitu, jika terdapatsepasang titik yang dihubungkan oleh lebih dari satu sisi.
Graf yang tidak mengandung loop dan/atau multi-sisidisebut graf sederhana atau lebih singkatnya disebut graf.
Sebuah sisi {u, v} sering dinotasikan dengan uv .
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Pengertian Graf (lanjutan)
Sebuah graf G mungkin mengandung loop, yaitu, sisi yangberbentuk {u, u}, dan/atau multi-sisi, yaitu, jika terdapatsepasang titik yang dihubungkan oleh lebih dari satu sisi.
Graf yang tidak mengandung loop dan/atau multi-sisidisebut graf sederhana atau lebih singkatnya disebut graf.
Sebuah sisi {u, v} sering dinotasikan dengan uv .
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Pengertian Graf (lanjutan)
Sebuah graf G mungkin mengandung loop, yaitu, sisi yangberbentuk {u, u}, dan/atau multi-sisi, yaitu, jika terdapatsepasang titik yang dihubungkan oleh lebih dari satu sisi.
Graf yang tidak mengandung loop dan/atau multi-sisidisebut graf sederhana atau lebih singkatnya disebut graf.
Sebuah sisi {u, v} sering dinotasikan dengan uv .
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Ordo
Definisi
Ordo dari sebuah graf G adalah banyaknya titik pada G.
Contoh
Graf berordo 7 dengan himpunan-titikV = {v1, v2, v3, v4, v5, v6, v7}.
v7v4v1
v2 v6
v5v3
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Ordo
Definisi
Ordo dari sebuah graf G adalah banyaknya titik pada G.
Contoh
Graf berordo 7 dengan himpunan-titikV = {v1, v2, v3, v4, v5, v6, v7}.
v7v4v1
v2 v6
v5v3
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Ketetanggaan dan Bersisian
Definisi
Misalkan u dan v merupakan titik-titik dari graf G. udikatakan bertetangga dengan v jika terdapat sebuah sisie yang menghubungkan u dan v, yaitu, e = uv.
Selanjutnya kita sebut v tetangga dari u.
Himpunan semua tetangga dari u disebut ketetanggaandari u dan dinotasikan dengan N(v).
Kedua titik u dan v dikatakan bersisian dengan sisi e.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Ketetanggaan dan Bersisian
Definisi
Misalkan u dan v merupakan titik-titik dari graf G. udikatakan bertetangga dengan v jika terdapat sebuah sisie yang menghubungkan u dan v, yaitu, e = uv.
Selanjutnya kita sebut v tetangga dari u.
Himpunan semua tetangga dari u disebut ketetanggaandari u dan dinotasikan dengan N(v).
Kedua titik u dan v dikatakan bersisian dengan sisi e.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Ketetanggaan dan Bersisian
Definisi
Misalkan u dan v merupakan titik-titik dari graf G. udikatakan bertetangga dengan v jika terdapat sebuah sisie yang menghubungkan u dan v, yaitu, e = uv.
Selanjutnya kita sebut v tetangga dari u.
Himpunan semua tetangga dari u disebut ketetanggaandari u dan dinotasikan dengan N(v).
Kedua titik u dan v dikatakan bersisian dengan sisi e.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Ketetanggaan dan Bersisian
Definisi
Misalkan u dan v merupakan titik-titik dari graf G. udikatakan bertetangga dengan v jika terdapat sebuah sisie yang menghubungkan u dan v, yaitu, e = uv.
Selanjutnya kita sebut v tetangga dari u.
Himpunan semua tetangga dari u disebut ketetanggaandari u dan dinotasikan dengan N(v).
Kedua titik u dan v dikatakan bersisian dengan sisi e.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Ketetanggaan dan Bersisian (lanjutan)
Contoh
Titik v1 bertetangga dengan titik v4; dan titik v3 bersisiandengan sisi v3v4 dan v3v5.
v7v4v1
v2 v6
v5v3
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Derajat
Definisi
Derajat dari titik v pada G adalah banyaknya titik-titik yangbertetangga dengan v, yaitu, jumlah semua tetangga dariv.
Jika sebuah titik v mempunyai derajat 0, dengan kata lainv tidak bertetangga dengan sembarang titik yang lain,maka v adalah titik terasing.
Sebuah titik berderajat 1 disebut titik ujung, atau daun.
Jika setiap titik dari graf G mempunyai derajat yang samamaka G disebut reguler.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Derajat
Definisi
Derajat dari titik v pada G adalah banyaknya titik-titik yangbertetangga dengan v, yaitu, jumlah semua tetangga dariv.
Jika sebuah titik v mempunyai derajat 0, dengan kata lainv tidak bertetangga dengan sembarang titik yang lain,maka v adalah titik terasing.
Sebuah titik berderajat 1 disebut titik ujung, atau daun.
Jika setiap titik dari graf G mempunyai derajat yang samamaka G disebut reguler.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Derajat
Definisi
Derajat dari titik v pada G adalah banyaknya titik-titik yangbertetangga dengan v, yaitu, jumlah semua tetangga dariv.
Jika sebuah titik v mempunyai derajat 0, dengan kata lainv tidak bertetangga dengan sembarang titik yang lain,maka v adalah titik terasing.
Sebuah titik berderajat 1 disebut titik ujung, atau daun.
Jika setiap titik dari graf G mempunyai derajat yang samamaka G disebut reguler.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Derajat
Definisi
Derajat dari titik v pada G adalah banyaknya titik-titik yangbertetangga dengan v, yaitu, jumlah semua tetangga dariv.
Jika sebuah titik v mempunyai derajat 0, dengan kata lainv tidak bertetangga dengan sembarang titik yang lain,maka v adalah titik terasing.
Sebuah titik berderajat 1 disebut titik ujung, atau daun.
Jika setiap titik dari graf G mempunyai derajat yang samamaka G disebut reguler.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Derajat (lanjutan)
Contoh
Derajat v4 adalah 4, v2 merupakan titik terasing, dan v1
merupakan titik ujung.
v7v4v1
v2 v6
v5v3
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Derajat (lanjutan)
Contoh
Graf reguler berderajat 4.
v7
v1 v3
v2
v4
v5
v6
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan
Definisi
Jalan v0 − vl pada graf G adalah sebuah barisanberhingga v0, e1, v1, e2, ..., el , vl bergantian titik dan sisipada G sedemikian hingga ei = vi−1vi untuk setiap i,1 ≤ i ≤ l .
Jalan juga dinotasikan dengan v0v1...vl .
Mungkin terdapat pengulangan titik dan sisi pada jalan.
Panjang jalan adalah banyaknya sisi pada jalan tersebut.
Jalan v0 − vl dikatakan tertutup jika v0 = vl .
Jika semua titik dari jalan v0 − vl berbeda, makadinamakan lintasan.
Sikel adalah lintasan yang tertutup.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan
Definisi
Jalan v0 − vl pada graf G adalah sebuah barisanberhingga v0, e1, v1, e2, ..., el , vl bergantian titik dan sisipada G sedemikian hingga ei = vi−1vi untuk setiap i,1 ≤ i ≤ l .
Jalan juga dinotasikan dengan v0v1...vl .
Mungkin terdapat pengulangan titik dan sisi pada jalan.
Panjang jalan adalah banyaknya sisi pada jalan tersebut.
Jalan v0 − vl dikatakan tertutup jika v0 = vl .
Jika semua titik dari jalan v0 − vl berbeda, makadinamakan lintasan.
Sikel adalah lintasan yang tertutup.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan
Definisi
Jalan v0 − vl pada graf G adalah sebuah barisanberhingga v0, e1, v1, e2, ..., el , vl bergantian titik dan sisipada G sedemikian hingga ei = vi−1vi untuk setiap i,1 ≤ i ≤ l .
Jalan juga dinotasikan dengan v0v1...vl .
Mungkin terdapat pengulangan titik dan sisi pada jalan.
Panjang jalan adalah banyaknya sisi pada jalan tersebut.
Jalan v0 − vl dikatakan tertutup jika v0 = vl .
Jika semua titik dari jalan v0 − vl berbeda, makadinamakan lintasan.
Sikel adalah lintasan yang tertutup.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan
Definisi
Jalan v0 − vl pada graf G adalah sebuah barisanberhingga v0, e1, v1, e2, ..., el , vl bergantian titik dan sisipada G sedemikian hingga ei = vi−1vi untuk setiap i,1 ≤ i ≤ l .
Jalan juga dinotasikan dengan v0v1...vl .
Mungkin terdapat pengulangan titik dan sisi pada jalan.
Panjang jalan adalah banyaknya sisi pada jalan tersebut.
Jalan v0 − vl dikatakan tertutup jika v0 = vl .
Jika semua titik dari jalan v0 − vl berbeda, makadinamakan lintasan.
Sikel adalah lintasan yang tertutup.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan
Definisi
Jalan v0 − vl pada graf G adalah sebuah barisanberhingga v0, e1, v1, e2, ..., el , vl bergantian titik dan sisipada G sedemikian hingga ei = vi−1vi untuk setiap i,1 ≤ i ≤ l .
Jalan juga dinotasikan dengan v0v1...vl .
Mungkin terdapat pengulangan titik dan sisi pada jalan.
Panjang jalan adalah banyaknya sisi pada jalan tersebut.
Jalan v0 − vl dikatakan tertutup jika v0 = vl .
Jika semua titik dari jalan v0 − vl berbeda, makadinamakan lintasan.
Sikel adalah lintasan yang tertutup.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan
Definisi
Jalan v0 − vl pada graf G adalah sebuah barisanberhingga v0, e1, v1, e2, ..., el , vl bergantian titik dan sisipada G sedemikian hingga ei = vi−1vi untuk setiap i,1 ≤ i ≤ l .
Jalan juga dinotasikan dengan v0v1...vl .
Mungkin terdapat pengulangan titik dan sisi pada jalan.
Panjang jalan adalah banyaknya sisi pada jalan tersebut.
Jalan v0 − vl dikatakan tertutup jika v0 = vl .
Jika semua titik dari jalan v0 − vl berbeda, makadinamakan lintasan.
Sikel adalah lintasan yang tertutup.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan
Definisi
Jalan v0 − vl pada graf G adalah sebuah barisanberhingga v0, e1, v1, e2, ..., el , vl bergantian titik dan sisipada G sedemikian hingga ei = vi−1vi untuk setiap i,1 ≤ i ≤ l .
Jalan juga dinotasikan dengan v0v1...vl .
Mungkin terdapat pengulangan titik dan sisi pada jalan.
Panjang jalan adalah banyaknya sisi pada jalan tersebut.
Jalan v0 − vl dikatakan tertutup jika v0 = vl .
Jika semua titik dari jalan v0 − vl berbeda, makadinamakan lintasan.
Sikel adalah lintasan yang tertutup.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jalan dan Lintasan (lanjutan)
Contoh
v1v2v6v7v4v2v3 adalah jalan dengan panjang 6 yang bukanlintasan,
v1v2v3v4v5v6 adalah lintasan dengan panjang 5,
v1v7v3v5v1 merupakan sebuah sikel.
v7
v1 v3
v2
v4
v5
v6
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jarak, Diameter dan Girth
Definisi
Jarak dari titik u ke titik v, dinotasikan dengan δ(u, v),adalah panjang dari lintasan terpendek dari titik u ke titik v.
Diameter dari graf G adalah jarak terpanjang diantarasembarang dua titik pada G.
Girth dari graf G adalah panjang sikel terpendek pada G.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jarak, Diameter dan Girth
Definisi
Jarak dari titik u ke titik v, dinotasikan dengan δ(u, v),adalah panjang dari lintasan terpendek dari titik u ke titik v.
Diameter dari graf G adalah jarak terpanjang diantarasembarang dua titik pada G.
Girth dari graf G adalah panjang sikel terpendek pada G.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jarak, Diameter dan Girth
Definisi
Jarak dari titik u ke titik v, dinotasikan dengan δ(u, v),adalah panjang dari lintasan terpendek dari titik u ke titik v.
Diameter dari graf G adalah jarak terpanjang diantarasembarang dua titik pada G.
Girth dari graf G adalah panjang sikel terpendek pada G.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Jarak, Diameter dan Girth (lanjutan)
Contoh
Jarak dari titik v1 ke v4 adalah 2.
Graf yang mempunyai diameter 2 dan girth 3.
v7
v1 v3
v2
v4
v5
v6
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Subgraf
Definisi
Sebuah graf H disebut subgraf dari G jika setiap titik dariH merupakan titik dari G, dan setiap sisi dari H merupakantitik dari G, dengan kata lain, V (H) ⊂ V (G) danE(H) ⊂ E(G).
Misalkan U merupakan subhimpunan dari V (G). Subgrafterinduksi G[U] adalah sebuah subgraf dari G yang terdiridari himpunan-titik U bersama dengan semua sisi uv padaG dimana u, v ∈ U.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Subgraf
Definisi
Sebuah graf H disebut subgraf dari G jika setiap titik dariH merupakan titik dari G, dan setiap sisi dari H merupakantitik dari G, dengan kata lain, V (H) ⊂ V (G) danE(H) ⊂ E(G).
Misalkan U merupakan subhimpunan dari V (G). Subgrafterinduksi G[U] adalah sebuah subgraf dari G yang terdiridari himpunan-titik U bersama dengan semua sisi uv padaG dimana u, v ∈ U.
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
Pengertian GrafJalan dan Lintasan
Jarak, Diameter dan GirthSubgraf
Subgraf (lanjutan)
Contoh
G1 merupakan sebuah subgraf terinduksi dari G,
G2 merupakan subgraf dari G tetapi tidak terinduksi
v1
v4
v2
v5
v6
v1 v3
v4
v2
v5
v7v6
v8
v3
v4
v2
v7
v8
G G1 G2
Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf
