Eksentrik Digraf Bilangan Ramsey (Titik dan Sisi) Matching Himpunan Kritis dalam

Pelabelan Graf

• Eksentrik digraf pada suatu graf adalah graf berarah (bisa bolak-balik) yang dapat merepresentasikan titik terjauh dari setiap titik ke titik lain.

• Eksentrik Digraf pertama kali diperkenalkan oleh Fred Buckley pada tahun 90-an.

• Setiap graf sederhana dan terhubung mempunyai eksentrik digraf

G

Jarak dari titik u ke titik v Misal G adalah graf dengan himp. Titik V(G) dan himp. Sisi E(G).

Jarak dari titik u ke titik v di G, dinotasikan dengan d(u,v) adalah panjang lintasan terpendek dari titik u ke titik v .

Beberapa Pengertian:

Maka d(v1,v2) = d(v1,v3) = d(v2,v4) =d(v3,v5) = d(v4,v5) = d(v5,v6) = 1

.

1v

3v

2v4v

6v

5v

d(v1,v4) = d(v2,v5) = d(v2,v6) = 2

d(v1,v6) = 3

Contoh: Asumsikan panjang setiap lintasan pada graf berikut adalah 1

Eksentrisitas Eksentrisitas titik v dinotasikan dengan ec(v)

adalah jarak terjauh (maksimal lintasan terpendek) dari titik v ke setiap titik di graf G.

Jadi ec(v) = maks{d(v,u) | uV(G)} .

Temukan ! ec(v2) = ... ec(v5) = .... ec(v3) = .... ec(v6 )= .... ec(v4) = ....

ec(v1) = maks{d(v1,v2), d(v1,v3), d(v1,v4),d(v1,v5), d(v1,v6)} = maks{1, 1, 2, 2, 3} =31v

3v

2v4v

6v

5v

Contoh:

Titik v disebut titik eksentrik dari u dinotasikan dengan

ec(u) = v , jika jarak dari v ke u sama dengan eksentrisitas dari

u atau d(u,v) = ec(u).

Titik Eksentrik

ec(v1)= 3 dengan titik eksentrik v6

ec(v2)= 2 dengan titik eksentrik v5 ,v6

Titik eksentrik dari v3? Titik eksentrik dari v4 ? Titik eksentrik dari v5 ? Titik eksentrik dari v6 ?

1v

3v

2v4v

6v

5v

Contoh:

Radius dari graf GRadius dari graf G, dinotasikan dengan r(G) merupakan

eksentrisitas minimum pada setiap titik di G. dapat ditulis: r(G) = min{ec(v)|vV(G)}.

1v

3v

2v 4v

6v

5v

Radius dari graf adalah r(G) =min{ec(v1), ec(v2), ec(v3) ,ec(v4), ec(v5), ec(v6)} =min{3,2,2,2,2,3} =2

Contoh : Jika diberikan graf G sbb:

Diameter dari graf G, dinotasikan dengan diam(G) adalah eksentrisitas maksimum pada setiap titik di G, dapat dituliskan sebagai

diam(G) = maks{ec(v)|vV(G)}.

Diameter dari graf G

Contoh:

1v

3v

2v4v

6v

5v

diam(G) = maks{ec(v1), ec(v2), ec(v3), ec(v4), ec(v5), ec(v6)} = maks{3,2,2,2,3} = 3

Titik central/Titik pusat dari graf G adalah titik v yang mempunyai eksentrisitas titik sama dengan radius G, ec(v) = r(G).

Subgraf dari graf G yang dibentuk oleh semua titik central G disebut central graf G dinotasikan dengan cen(G).

Graf yang hanya memuat satu titik sentral disebut graf unicentral

1v

3v

2v 4v

6v

5v

Karena ec(v2) = ec(v3) = ec(v4) = ec(v5) = r(G)=2 Sehingga titik pusat dari G adalah titik v1, v2,v3 dan v4

Contoh:

dan cen(G) adalah :

3v

2v4v

5v

Eksentrik DigrafEksentrik digraf pada graf G, dinotasikan dengan ED(G),

didefinisikan sebagai digraf yang mempunyai himpunan titik

yang sama dengan G atau V(ED(G))=V(G) dan himpunan

sisi berarah A(ED(G)) yang elemen-elemennya merupakan

sisi-sisi berarah uv yang menghubungkan titik u ke v jika

v adalah titik eksentrik dari u, dapat ditulis

A(ED(G))={uv|vec(u)=v}.

V(G)={v1,v2,v3,v4,v5,v6}

V(ED(G)=V(G)A(ED(G))={v1v6,v2v5,v2v6,

v3v4, v3v6, v4v1,

v4v3,v5v1, v5v2, v6v1,}

Beberapa jenis graf yang telah dikaji eksentrik digrafnya

antara lain :o Graf Lintasan Pn, o Graf Sikel Cn, o Graf Lengkap Kn, o Graf Bintang Sn, o Graf Bipartit lengkap Kn,m , o Fan graph Fn, o Wheel graph Wn , o Prism graph Yn,m

Graf Prisma Yn,m adalah graf hasil perkalian kartesius

(Graph cartesian product) antara graf sikel berorder n dengan graf lintasan berorder m (Yn,m = Cn x Pm).

Y4,3

Eksentrik Digraf pada graf Roda Wn :

Eksentrik Digraf pada graf Yn,m :

Eksentrik digraf pada W5

Graf Prisma Y4,3 dan eksentrik digrafnya

Perhatikan graf G berikut.

Rad(G)=3

Diam(G)=5

Cen(G) : v6 v7

o Misal G(V, E) dan u,v,w di V(G) 1. d(u,u) = 0

2. d(u,v) > 0 jika u v 3. d(u,v) = d(v,u) (Sifat Simetri) 4. d((u,v) ≤ d(u,w) + d(w, v) (Sifat Ketaksamaan Segitiga)

o Untuk setiap graf terhubung G, rad(G) ≤ diam(G) ≤ 2rad(G)

o Untuk setiap dua titik yang bertetangga u dan v dalam graf terhubung adalah maka ec(u) - ec(v) ≤ 1

o Setiap graf adalah pusat dari beberapa graf

1. Perhatikan graf H berikut. Temukan eksentrisitas dari setiap titik di graf H, rad(H), diam (H) dan Cen(H)

2. Jelaskan bahwa untuk setiap dua titik u dan v dalam graf

terhubung maka ec(u) - ec(v) ≤ d(u,v)

3. Misal u, v titik yang bertetangga dalam graf terhubung G.

tunjukkand(u,x)-d(v,x) ≤ 1 untuk setiap titik x di G

1.For each integer n ≥ 3, construct a graph

G of order n such that

diam G = 2 rad G

2. Untuk setiap bilangan bulat n >1,

konstruksikan sebuah graf G

berorder n , sehingga untuk 0 < k < n

ada dua titik x,y di G dengan

d(x,y) = k

3. Misal G graf terhubung dan u, v di

V(G) .

Tunjukkan bahwa untuk setiap

bilangan bulat k dengan 0 < k < d(u,v)

ada w di V(G) sedemikian sehingga

d(u,w) = k

1. Bagiamana masalah eksentrik digraf untuk jenis-jenis graf yang lain ?

2. Bagaimana aplikasi teori dalam kehidupan sehari-hari (real world)

3. Investigasi radius dan diameter dalam graf reguler terhubung !