6. Turnamen Round-Robin
Turnamen yang setiap tim bertanding dengan tim lainnya hanya sekali disebut turnamen round-robin.
Turnamen semacam itu dimodelkan dengan graf berarah, yang dalam hal ini simpul menyatakan tiap tim
yang bertanding, dan busur menyatakan pertandingan. Busur (a, b) berarti tim a berhasil memukul tim b.
Gambar 4.7 memperlihatkan turnamen round-robin untuk 6 buah tim. Tim 1 tidak terkalahkan, sedangkan
tim 3 tidak pernah menang.
 |
| Gambar 4.7 Turnamen round-robin |
Contoh terapan graf yang lain adalah menyatakan aliran informasi dalam pengolahan sinyal dan aliran massa
dalam industri kimia. Graf juga berguna memodelkan sesuatu yang abstrak, seperti struktur perusahaan,
tingkatan sosial, pohon keluarga, aliran kerja dalam proyek, perencanaan dan manajemen proyek,
perpindahan dalam permainan (game), dan langkah-langkah pemecahan masalah. Terapan yang terakhir ini
merupakan kemampuan dasar yang harus dikuasai dalam bidang kecerdasan buatan (artificial intelligence).
7. Terminologi Dasar
Kita akan sering menggunakan terminologi (istilah) yang berkaitan dengan graf. Di bawah ini didefinisikan
beberapa terminologi yang sering dipakai. Contoh graf pada Gambar 8.12 akan digunakan untuk
memperjelas terminologi yang kita definisikan. Graf yang pertama, G1, adalah graf sederhana, G2 adalah graf
semu yang mengandung sisi ganda maupun gelang, sedangkan G3 adalah graf dengan sebuah simpul yang
terpisah dari simpul lainnya. Ketiga buah graf ini adalah graf tidak-berarah. Untuk terminologi yang
menyangkut graf berarah, contoh grafnya akan digambarkan pada waktu pembahasan
 |
| Gambar 4.8 Tiga buah graf, G1, G2, dan G3 |
1. Bertetangga (Adjacent)
Dua buah simpul pada graf tak-berarah G dikatakan bertetangga bila keduanya terhubung
langsung dengan sebuah sisi. Dengan kata lain, vj bertetangga dengan vk jika (vj, vk) adalah sebuah sisi pada graf G.
 |
| Gambar 5.1 |
simpul 1 bertetangga dengan simpul 2 dan 3,
simpul 1 tidak bertetangga dengan simpul 4.
2. Bersisian (Incident)
Untuk sembarang sisi e = (vj, vk), sisi e dikatakan bersisian dengan simpul vj dan simpul vk
 |
| Gambar 5.2 |
sisi (2, 3) bersisian dengan simpul 2 dan simpul 3, sisi (2,
4) bersisian dengan simpul 2 dan simpul 4, tetapi sisi (1, 2)
tidak bersisian dengan simpul 4.
3. Simpul Terpencil (Isolated Vertex)
Simpul
terpencil ialah simpul yang tidak mempunyai sisi yang bersisian
dengannya. Atau, dapat juga dinyatakan bahwa simpul terpencil adalah
simpul yang tidak satupun bertetangga dengan simpulsimpul lainnya.
 |
| Gambar 5.3 Simpul terpencil |
4. Graf Kosong (Null Graph atau Empty Graph)
Graf yang himpunan sisinya merupakan himpunan kosong disebut sebagai graf kosong dan
ditulis sebagi Nn , yang dalam hal ini n adalah jumlah simpul.
 |
| Gambar 5.4 Graf kosong N5 |
5. Derajat (Degree)
Derajat suatu simpul pada graf tak-berarah adalah jumlah sisi yang bersisian dengan simpul
Notasi: d(v) menyatakan derajat simpul v.
Simpul terpencil adalah simpul dengan d(v) = 0, karena tidak ada satupun sisi yang bersisian dengan simpul
tersebut. Pada Gambar 8.12(c), d(5) = 0.
Sisi gelang (loop) dihitung berderajat dua.
Alasan mengapa gelang mengkontribusikan dua untuk derajat simpulnya adalah karena gelang
direpresentasikan sebagai (v, v), dan simpul v bersisian dua kali pada sisi (v, v).
Simpul yang berderajat satu disebut anting-anting (pendant vertex). Dengan kata lain, anting-anting hanya
bertetangga dengan sebuah simpul. Pada Gambar 8.13(c), d(4) = 1, karena itu simpul 4 adalah anting-anting.
din(v) =
derajat-masuk (in-degree)
= jumlah busur yang masuk ke simpul v
dout(v) =
derajat-keluar (out-degree)
= jumlah busur yang keluar dari simpul v
d(v) = din(v) + dout(v)
Jumlah
derajat semua simpul pada suatu graf adalah genap, yaitu dua kali
jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E), maka
( catatan: ingatlah 2 E selalu bernilai genap)
Lemma
ini dikenal dengan lemma jabat tangan (handshaking lemma). Hal ini
disebabkan oleh setiap sisi dihitung dua kali, yaitu pada ujung kiri
sebagai bagian dari simpul kiri dan pada ujung kanan dihitung sebagai
bagian dari simpul kanan. Layaknya orang berjabat tangan, maka jumlah
tangan yang berjabatan adalah genap dan jumlah tangan yang berjabatan
adalah dua kali jumlah jabatan tangan yang terjadi [DUL94]. Catatlah
bahwa Lemma Jabat Tangan juga benar untuk graf berarah, yang dalam hal
ini d(v) = din(v) + dout(v).
8. Lintasan (Path)
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah
barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian
sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G.
Jika
graf yang ditinjau adalah graf sederhana, maka kita cukup menuliskan
lintasan sebagai barisan simpu-lsimpul saja: v0, v1, v2, ... , vn –1, vn
, karena antara dua buah simpul berturutan di dalam lintasan tersebut
hanya ada satu sisi.
7. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.
Pada Gambar 8.12(a), 1, 2, 3, 1 adalah sebuah sirkuit. Panjang sirkuit adalah jumlah sisi di dalam sirkuit tersebut.
V. Representasi Graph
1. Matriks
Ketetanggaan (adjacency matrix)
2. Matriks Bersisian (incidency matrix)
3. Senarai Ketetanggaan (adjacency list)
