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