PROGRAM GRAF BERARAH,TAK BERARAH DAN BERBOBOT

—  PROGRAM GRAF BERARAH,TAK BERARAH DAN BERBOBOT

—  GRAPH

• Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :

G = (V, E)

Dimana :

                G = Graph

                V = Simpul atau Vertex, atau Node, atau Titik

                E = Busur atau Edge, atau arc

—  Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut.

—   3. Indegree sebuah simpul pada graph berarah
adalah jumlah busur yang kepalanya incident dengan
simpul tersebut, atau jumlah busur yang 􀁬masuk􀁺􀀁atau
menuju simpul tersebut.

  4. Outdegree sebuah simpul pada graph berarah
adalah jumlah busur yang ekornya incident dengan
simpul tersebut, atau jumlah busur yang 􀁬keluar􀁺􀀁atau
berasal dari simpul tersebut.

•       Sebuah graph mungkin hanya terdiri                                      
dari satu simpul.

• Sebuah graph belum tentu semua
simpulnya terhubung dengan busur.

• Sebuah graph mungkin mempunyai
simpul yang tak terhubung dengan
simpul yang lain.

• Sebuah graph mungkin semua
simpulnya saling berhubungan

—  Berdasarkan orientasi arah pada sisi dan bobotnya, maka secara umum graf dapat dibedakan
atas tiga jenis yaitu:

1. GRAPH BERARAH (directed graph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Secara
umum sisi berarah disebut dengan busur (arc). Pada graf berarah (u,v) dan (v,u)
menyatakan dua buah busur yang berbeda, dalam arti kata bahwa (u,v) ¹ (v,u).

— 

Graf berarah sering dipakai untuk menggambarkan aliran proses, peta lintas
kota dan lain sebagainya. Sehingga pada graf berarah gelang atau looping
diperbolehkan tetapi sisi ganda tidak diperbolehkan.

—  Contoh programnya:

—  Uses wincrt;
type titikList= ^Titik;
garisList= ^Garis;{simpuluntuk senarai Titik}
Titik= record
namaTitik: char;
NextTitik: TitikList;
KeGaris: GarisList;
end;
{simpul untuk senarai garis }Garis= record panjang: word;
KeTitik: TitikList;
NextGaris: GarisList;
end;
varT : text;
T1,T2: Byte; P : word;
GraphAwal: TitikList
End.

—  2. GRAPH tak BERARAH (undirected graph atau non-directed graph) :

2. Graf tidak berarah

—  Yaitu Graf yang setiap sisinya tidak mempunyai arah anak panah tetapi memiliki bobot pada

—  setiap sisinya. Urutan pasangan simpul yang terhubung oleh sisi tidak diperhatikan.

—  Sehingga (u,v) = (v,u) adalah sisi yang sama.

— 
3. GRAPH Berbobot (Weighted Graph).

—  graf berbobot merupakan suatu graf tanpa busur parallel dimana setiap busurnya berhubungan dengan suatu bilangan riil tak negatif yang menyatakan bobot busur (w(a)) tersebuT.
Di dalam model graf, ada informasi yang ditambahkan pada busur graf. Misalnya pada graf yang menggambarkan antara kota-kota, dapat ditambahkan sebuah bilangan pada setiap busur untuk menujukkan jalur antara kedua kota yang dibutuhkan oleh busur tersebut.
 

—  Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki
bobot.
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui
sebuah jalan, dll.
 

Ø  Panjang busur (atau bobot) mungkin tidak digambarkan secara panjang yang proposional dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.

Contoh program

—  HASILNYA

SEKIAN PRESENTASI KAMI

TERIMAKASIH