Outline

Konsep Dasar Teori GrafDrs. Slamin, M.Comp.Sc.,Ph.D

Program Studi Pendidikan Matematika Universitas Jember

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Outline

Outline

1

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

2

3

4

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Outline

Outline

1

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

2

3

4

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Outline

Outline

1

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

2

3

4

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Outline

Outline

1

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

2

3

4

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Pengertian GrafDenisi Sebuah graf tak berarah G biasanya disebut graf saja didenisikan sebagai sebuah pasangan himpunan (V (G), E (G)), dimana V (G) adalah himpunan berhingga tak kosong dari elemen yang disebut titik, dan E (G) adalah sebuah 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) disebut himpunan-sisi dari G.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Pengertian GrafDenisi Sebuah graf tak berarah G biasanya disebut graf saja didenisikan sebagai sebuah pasangan himpunan (V (G), E (G)), dimana V (G) adalah himpunan berhingga tak kosong dari elemen yang disebut titik, dan E (G) adalah sebuah 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) disebut himpunan-sisi dari G.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Pengertian Graf (lanjutan)Contoh Graf dengan himpunan-titik V = {v1 , v2 , v3 , v4 , v5 , v6 , v7 } dan himpunan-sisi E = {v1 v4 , v4 v3 , v3 v5 , v5 v4 , v4 v7 }.

v3 v2 v1 v4

v5 v6 v7

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Pengertian Graf (lanjutan)

Sebuah graf G mungkin mengandung loop, yaitu, sisi yang berbentuk {u, u}, dan/atau multi-sisi, yaitu, jika terdapat sepasang titik yang dihubungkan oleh lebih dari satu sisi. Graf yang tidak mengandung loop dan/atau multi-sisi disebut 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Pengertian Graf (lanjutan)

Sebuah graf G mungkin mengandung loop, yaitu, sisi yang berbentuk {u, u}, dan/atau multi-sisi, yaitu, jika terdapat sepasang titik yang dihubungkan oleh lebih dari satu sisi. Graf yang tidak mengandung loop dan/atau multi-sisi disebut 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Pengertian Graf (lanjutan)

Sebuah graf G mungkin mengandung loop, yaitu, sisi yang berbentuk {u, u}, dan/atau multi-sisi, yaitu, jika terdapat sepasang titik yang dihubungkan oleh lebih dari satu sisi. Graf yang tidak mengandung loop dan/atau multi-sisi disebut 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

OrdoDenisi Ordo dari sebuah graf G adalah banyaknya titik pada G. Contoh Graf berordo 7 dengan himpunan-titik V = {v1 , v2 , v3 , v4 , v5 , v6 , v7 }.

v3 v2 v1Drs. Slamin, M.Comp.Sc.,Ph.D

v5 v6 v4 v7

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

OrdoDenisi Ordo dari sebuah graf G adalah banyaknya titik pada G. Contoh Graf berordo 7 dengan himpunan-titik V = {v1 , v2 , v3 , v4 , v5 , v6 , v7 }.

v3 v2 v1Drs. Slamin, M.Comp.Sc.,Ph.D

v5 v6 v4 v7

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Ketetanggaan dan Bersisian

Denisi Misalkan u dan v merupakan titik-titik dari graf G. u dikatakan bertetangga dengan v jika terdapat sebuah sisi e yang menghubungkan u dan v, yaitu, e = uv. Selanjutnya kita sebut v tetangga dari u. Himpunan semua tetangga dari u disebut ketetanggaan dari 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Ketetanggaan dan Bersisian

Denisi Misalkan u dan v merupakan titik-titik dari graf G. u dikatakan bertetangga dengan v jika terdapat sebuah sisi e yang menghubungkan u dan v, yaitu, e = uv. Selanjutnya kita sebut v tetangga dari u. Himpunan semua tetangga dari u disebut ketetanggaan dari 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Ketetanggaan dan Bersisian

Denisi Misalkan u dan v merupakan titik-titik dari graf G. u dikatakan bertetangga dengan v jika terdapat sebuah sisi e yang menghubungkan u dan v, yaitu, e = uv. Selanjutnya kita sebut v tetangga dari u. Himpunan semua tetangga dari u disebut ketetanggaan dari 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Ketetanggaan dan Bersisian

Denisi Misalkan u dan v merupakan titik-titik dari graf G. u dikatakan bertetangga dengan v jika terdapat sebuah sisi e yang menghubungkan u dan v, yaitu, e = uv. Selanjutnya kita sebut v tetangga dari u. Himpunan semua tetangga dari u disebut ketetanggaan dari 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Ketetanggaan dan Bersisian (lanjutan)Contoh Titik v1 bertetangga dengan titik v4 ; dan titik v3 bersisian dengan sisi v3 v4 dan v3 v5 .

v3 v2 v1 v4

v5 v6 v7

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

DerajatDenisi Derajat dari titik v pada G adalah banyaknya titik-titik yang bertetangga dengan v, yaitu, jumlah semua tetangga dari v. Jika sebuah titik v mempunyai derajat 0, dengan kata lain v 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 sama maka G disebut reguler.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

DerajatDenisi Derajat dari titik v pada G adalah banyaknya titik-titik yang bertetangga dengan v, yaitu, jumlah semua tetangga dari v. Jika sebuah titik v mempunyai derajat 0, dengan kata lain v 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 sama maka G disebut reguler.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

DerajatDenisi Derajat dari titik v pada G adalah banyaknya titik-titik yang bertetangga dengan v, yaitu, jumlah semua tetangga dari v. Jika sebuah titik v mempunyai derajat 0, dengan kata lain v 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 sama maka G disebut reguler.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

DerajatDenisi Derajat dari titik v pada G adalah banyaknya titik-titik yang bertetangga dengan v, yaitu, jumlah semua tetangga dari v. Jika sebuah titik v mempunyai derajat 0, dengan kata lain v 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 sama maka G disebut reguler.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Derajat (lanjutan)Contoh Derajat v4 adalah 4, v2 merupakan titik terasing, dan v1 merupakan titik ujung.

v3 v2 v1 v4

v5 v6 v7

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Derajat (lanjutan)Contoh Graf reguler berderajat 4.

v2 v1 v7 v6 v5 v4 v3

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan LintasanDenisi Jalan v0 vl pada graf G adalah sebuah barisan berhingga v0 , e1 , v1 , e2 , ..., el , vl bergantian titik dan sisi pada G sedemikian hingga ei = vi1 vi untuk setiap i, 1 i l. Jalan juga dinotasikan dengan v0 v1 ...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, maka dinamakan lintasan. Sikel adalah lintasan yang tertutup.Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan LintasanDenisi Jalan v0 vl pada graf G adalah sebuah barisan berhingga v0 , e1 , v1 , e2 , ..., el , vl bergantian titik dan sisi pada G sedemikian hingga ei = vi1 vi untuk setiap i, 1 i l. Jalan juga dinotasikan dengan v0 v1 ...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, maka dinamakan lintasan. Sikel adalah lintasan yang tertutup.Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan LintasanDenisi Jalan v0 vl pada graf G adalah sebuah barisan berhingga v0 , e1 , v1 , e2 , ..., el , vl bergantian titik dan sisi pada G sedemikian hingga ei = vi1 vi untuk setiap i, 1 i l. Jalan juga dinotasikan dengan v0 v1 ...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, maka dinamakan lintasan. Sikel adalah lintasan yang tertutup.Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan LintasanDenisi Jalan v0 vl pada graf G adalah sebuah barisan berhingga v0 , e1 , v1 , e2 , ..., el , vl bergantian titik dan sisi pada G sedemikian hingga ei = vi1 vi untuk setiap i, 1 i l. Jalan juga dinotasikan dengan v0 v1 ...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, maka dinamakan lintasan. Sikel adalah lintasan yang tertutup.Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan LintasanDenisi Jalan v0 vl pada graf G adalah sebuah barisan berhingga v0 , e1 , v1 , e2 , ..., el , vl bergantian titik dan sisi pada G sedemikian hingga ei = vi1 vi untuk setiap i, 1 i l. Jalan juga dinotasikan dengan v0 v1 ...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, maka dinamakan lintasan. Sikel adalah lintasan yang tertutup.Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan LintasanDenisi Jalan v0 vl pada graf G adalah sebuah barisan berhingga v0 , e1 , v1 , e2 , ..., el , vl bergantian titik dan sisi pada G sedemikian hingga ei = vi1 vi untuk setiap i, 1 i l. Jalan juga dinotasikan dengan v0 v1 ...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, maka dinamakan lintasan. Sikel adalah lintasan yang tertutup.Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan LintasanDenisi Jalan v0 vl pada graf G adalah sebuah barisan berhingga v0 , e1 , v1 , e2 , ..., el , vl bergantian titik dan sisi pada G sedemikian hingga ei = vi1 vi untuk setiap i, 1 i l. Jalan juga dinotasikan dengan v0 v1 ...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, maka dinamakan lintasan. Sikel adalah lintasan yang tertutup.Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jalan dan Lintasan (lanjutan)Contoh v1 v2 v6 v7 v4 v2 v3 adalah jalan dengan panjang 6 yang bukan lintasan, v1 v2 v3 v4 v5 v6 adalah lintasan dengan panjang 5, v1 v7 v3 v5 v1 merupakan sebuah sikel.

v2 v1 v7 v6 v5Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

v3

v4

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jarak, Diameter dan Girth

Denisi 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 diantara sembarang 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jarak, Diameter dan Girth

Denisi 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 diantara sembarang 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jarak, Diameter dan Girth

Denisi 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 diantara sembarang 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 Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Jarak, Diameter dan Girth (lanjutan)Contoh Jarak dari titik v1 ke v4 adalah 2. Graf yang mempunyai diameter 2 dan girth 3.

v2 v1 v7 v6 v5Drs. Slamin, M.Comp.Sc.,Ph.D Konsep Dasar Teori Graf

v3

v4

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Subgraf

Denisi Sebuah graf H disebut subgraf dari G jika setiap titik dari H merupakan titik dari G, dan setiap sisi dari H merupakan titik dari G, dengan kata lain, V (H) V (G) dan E (H) E (G). Misalkan U merupakan subhimpunan dari V (G). Subgraf terinduksi G[U] adalah sebuah subgraf dari G yang terdiri dari himpunan-titik U bersama dengan semua sisi uv pada G dimana u, v U.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Subgraf

Denisi Sebuah graf H disebut subgraf dari G jika setiap titik dari H merupakan titik dari G, dan setiap sisi dari H merupakan titik dari G, dengan kata lain, V (H) V (G) dan E (H) E (G). Misalkan U merupakan subhimpunan dari V (G). Subgraf terinduksi G[U] adalah sebuah subgraf dari G yang terdiri dari himpunan-titik U bersama dengan semua sisi uv pada G dimana u, v U.

Drs. Slamin, M.Comp.Sc.,Ph.D

Konsep Dasar Teori Graf

Pengertian Graf Jalan dan Lintasan Jarak, Diameter dan Girth Subgraf

Subgraf (lanjutan)Contoh G1 merupakan sebuah subgraf terinduksi dari G, G2 merupakan subgraf dari G tetapi tidak terinduksi

v2 v6 v1 v5 G v4Drs. Slamin, M.Comp.Sc.,Ph.D

v2 v7 v3 v1 v8 G1 v4Konsep Dasar Teori Graf

v2 v7 v3

v6

v5 v4

v8 G2