Graph adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik ( node ) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).

Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul bisa diberi nomor atau label dan ruas dapat diberi nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi komputer. Contoh, graph dengan simpul yang merepresentasikan kota dan ruas merepresentasikan jarak yang ditempuh diantara kota-kota tsb. (atau harga tiket pesawat antara kota-kota tsb.) , dapat digunakan sebagai “transportation network” untuk mempelajari total jarak (atau harga) dari suatu perjalanan dengan banyak kota pemberhentian. Satu kemungkinan pertanyaan yang bisa muncul adalah “Jalur mana yang terpendek dengan satu atau lebih tempat pemberhentian, yang menghubungkan kota tertentu menuju kota tertentu lainnya dalam transportation network tersebut ?”.
Dalam kehidupan sehari-hari maupun dalam bidang akademis banyak persoalan yang dimodelkan dengan graph. Graph dipakai untuk membantu pemecahan masalah. Dari model graph yang dibuat, suatu masalah dapat dipahami menjadi lebih mudah. Untuk kemudian diturunkan metode pemecahannya.



Kelahiran Teori Graph

Gbr1. Jembatan Konigsberg
Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graph (th. 1736). Masalah Jembatan Konigsberg adalah : “ apakah mungkin melalui tujuh buah jembatan masing-masing tepat satu kali. Dan kembali lagi ke tempat semula ?” . Tak seorangpun yang dapat memecahkan masalah ini. Barulah Euler yang pertama kali menemukan jawabannya. Ia memodelkan masalah dengan memodelkannya ke dalam graph. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakannya sebagai simpul (vertex) dan jembatan sebagai sisi. Graph dibuat oleh Euler diperlihatkan pada gambar dibawah atas.
Jawabannya adalah : Orang tidak mungkin berjalan melalui ketujuh jembatan masing-masing satu kali dan kembali ke tempat asal keberangkatan. Singkatnya, tidak terdapat siklus Euler pada Graph tersebut.
Graph yang memenuhi kondisi diatas tersebut kemudian dikenal dengan nama Graph Euler dan perjalanannya disebut perjalanan euler.
Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
Perjalanan Euler akan terjadi, jika :
- Graf terhubung.
- Banyaknya ruas yang datang pada setiap simpul adalah genap
Jenis Graph
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan menjadi dua jenis:
1. Graph sederhana (simple graph).
Graph yang tidak mengandung gelung maupun sisi-ganda dinamakan graph sederhana.
2. Graph tak-sederhana (unsimple-graph/multigraph).
Graph yang mengandung ruas ganda atau gelung dinamakan graph tak-sederhana (unsimple graph atau multigrapf).
Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:
1. Graph berhingga (limited graph)
Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.
2. Graph tak-berhingga (unlimited graph)
Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:
1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.
2. Graph berarah (directed graph atau digraph)

Graph adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik ( node ) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).

Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul bisa diberi nomor atau label dan ruas dapat diberi nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi komputer. Contoh, graph dengan simpul yang merepresentasikan kota dan ruas merepresentasikan jarak yang ditempuh diantara kota-kota tsb. (atau harga tiket pesawat antara kota-kota tsb.) , dapat digunakan sebagai “transportation network” untuk mempelajari total jarak (atau harga) dari suatu perjalanan dengan banyak kota pemberhentian. Satu kemungkinan pertanyaan yang bisa muncul adalah “Jalur mana yang terpendek dengan satu atau lebih tempat pemberhentian, yang menghubungkan kota tertentu menuju kota tertentu lainnya dalam transportation network tersebut ?”.
Dalam kehidupan sehari-hari maupun dalam bidang akademis banyak persoalan yang dimodelkan dengan graph. Graph dipakai untuk membantu pemecahan masalah. Dari model graph yang dibuat, suatu masalah dapat dipahami menjadi lebih mudah. Untuk kemudian diturunkan metode pemecahannya.



Kelahiran Teori Graph

Gbr1. Jembatan Konigsberg
Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graph (th. 1736). Masalah Jembatan Konigsberg adalah : “ apakah mungkin melalui tujuh buah jembatan masing-masing tepat satu kali. Dan kembali lagi ke tempat semula ?” . Tak seorangpun yang dapat memecahkan masalah ini. Barulah Euler yang pertama kali menemukan jawabannya. Ia memodelkan masalah dengan memodelkannya ke dalam graph. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakannya sebagai simpul (vertex) dan jembatan sebagai sisi. Graph dibuat oleh Euler diperlihatkan pada gambar dibawah atas.
Jawabannya adalah : Orang tidak mungkin berjalan melalui ketujuh jembatan masing-masing satu kali dan kembali ke tempat asal keberangkatan. Singkatnya, tidak terdapat siklus Euler pada Graph tersebut.
Graph yang memenuhi kondisi diatas tersebut kemudian dikenal dengan nama Graph Euler dan perjalanannya disebut perjalanan euler.
Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
Perjalanan Euler akan terjadi, jika :
- Graf terhubung.
- Banyaknya ruas yang datang pada setiap simpul adalah genap
Jenis Graph
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan menjadi dua jenis:
1. Graph sederhana (simple graph).
Graph yang tidak mengandung gelung maupun sisi-ganda dinamakan graph sederhana.
2. Graph tak-sederhana (unsimple-graph/multigraph).
Graph yang mengandung ruas ganda atau gelung dinamakan graph tak-sederhana (unsimple graph atau multigrapf).
Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:
1. Graph berhingga (limited graph)
Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.
2. Graph tak-berhingga (unlimited graph)
Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:
1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.
2. Graph berarah (directed graph atau digraph)

array

Array adalah suatu tipe data terstruktur yang terdapat dalam memori yang
terdiri dari sejumlah elemen (tempat) yang mempunyai tipe data yang sama dan
merupakan gabungan dari beberapa variabel sejenis serta memiliki jumlah
komponen yang jumlahnya tetap.
Fungsi array adalah sebagai langkah efisiensi penggunan memori komputer, sebab data elemen array dialokasikan pada suatu deretan sel memori tertentu. Selain itu agar memudahkan programmer dalam menyusun aplikasi yang berhubungan dengan banyak data terutama dalam masalah pencarian dan pengurutan data secara cepat.

Cara mendeklarasikan array diawali dengan nama variabel array diikuti dengan indeks array yang dituliskan didalam tanda “[]” , diikuti dengan kata cadangan of dan tipe data yang dibutuhkan.
Tiga hal yang harus diketahui dalam mendeklarasi array:
• Type data array
• Nama variable array
• Subkrip / index array
Cara alokasi penggunaan array dibagi menjadi dua:
a) Array Static (Static Array)
Array static adalah model pendeklarasian array dimana tipe data yang digunakan mempunyai nilai yang tetap. Nilai yang digunakan untuk menentukan jangkauan pada umumnya bernilai integer. Array Static juga bisa disebut Array dengan deklarasi tipe indeks subrange integer.
b) Array Dinamis (Dynamic arrays)
Larik atau array dinamis merupakan array yang tidak mempunyai suatu jangkauan atau ukuran yang tetap. Tetapi ketika program dijalankan maka memori untuk suatu array dinamis direalokasikan ketika kita menugaskan suatu nilai kepada array. Dynamic-Array jenis ditandai oleh konstruksi (menyangkut) format.

Mendefinisikan array artinya menentukan besar array yang diinginkan. Setelah pendefinisian array, maka memori akan dialokasikan untuk menyimpan data dari array. Besar memori yang dialokasikan tergantung dari tipe data variabel array dan jumlah elemen array yang didefinisikan.
Keunggulan dan Kelemahan Array adalah
a. Keunggulan array adalah sebagai berikut:
• Array sangat cocok untuk mengakses acak. Sembarangan elemen di array acak secara langsung tanpa melalui elemen-elemen lain.
• Jika berada di suatu suatu elemen, maka sangat mudah menelusuri keelemen-elemen tetangga baik elemen pendahulu atau elemen penerus.
• Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga, maka penggunaan penyimpanannya sangat efisien,
• Sebagai tipe data dibandingkan dengan penggunaan tipe data yang lain adalah kemampuannya yang dapat mengumpulkan beberapa data yang bertipe sama dalam satu variabel, sehingga dalam pembuatan program yang terdiri dari beberapa tipe yang sama, tidak membutuhkan banyak variable.
b. Kelemahan array adalah sebagai berikut:
• Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen adlah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain.
• Kebanyakan bahasa pemrograman mengimplementasikan array static yang sulit diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi terus menerus, maka representasi statis.
• Tidak efisien dalam penggunaan memory.
• Pada suatu aplikasi, representasi statis tidak dimungkinkan..
Jenis-jenis array adalah
a) Array Dimensi Satu (One Dimensional Array)
Merupakan sebuah variabel yang menyimpan sekumpulan data yang memiliki tipe sama dan elemen yang akan diakses hanya melalui 1 indeks atau subskrip.
b) Array Dimensi Dua (Two Dimensional Array)
Merupakan sebuah variabel yang menyimpan sekumpulan data yang memiliki type sama dan elemen yang akan diakses melalui 2 indeks atau subskrip yaitu indeks baris dan indeks kolom.
c) Array multidimen
Selain array satu dimensi dan array dua dimensi, dapat juga membuat array multidimensi pada Java. Array multidimensi merupakan array yang terdiri dari array yang tidak terbatas hanya dua dimensi saja.