Teori Graf — Simpul, Sisi & Konsep Dasar

Teori graf adalah cabang ilmu yang mempelajari graf, yaitu struktur yang tersusun dari simpul dan sisi. Simpul adalah objek, dan sisi menunjukkan hubungan antara dua objek.

Jika Anda mencari dasar-dasar teori graf, mulailah dari gagasan ini: graf adalah cara yang rapi untuk memodelkan keterhubungan. Orang dalam jejaring sosial, kota yang dihubungkan oleh jalan, dan halaman web yang saling tertaut semuanya dapat direpresentasikan dengan graf.

Apa Arti Graf Dalam Matematika

Dalam graf tak berarah, sebuah sisi menyatakan bahwa dua simpul terhubung, dan hubungan itu tidak memiliki arah. Jika $A$ terhubung ke $B$, maka $B$ juga terhubung ke $A$.

Dalam graf berarah, sisi memang memiliki arah, sehingga $A \to B$ dan $B \to A$ adalah pernyataan yang berbeda. Banyak contoh untuk pemula menggunakan graf sederhana tak berarah, yang berarti tidak ada loop dan tidak ada sisi berulang antara dua simpul yang sama.

Kondisi itu penting karena definisi sering kali pertama kali diperkenalkan dalam konteks graf sederhana tak berarah. Jika jenis graf berubah, makna istilah-istilahnya juga bisa berubah.

Istilah Dasar Teori Graf yang Perlu Anda Ketahui

Simpul dan sisi

Simpul adalah hal yang ingin Anda lacak. Sisi adalah hubungan yang ingin Anda lacak.

Jika sebuah graf memodelkan kota dan jalan, maka kota adalah simpul dan jalan adalah sisi.

Derajat

Dalam graf tak berarah, derajat sebuah simpul adalah banyaknya sisi yang menempel padanya.

Jika satu kota memiliki jalan ke tiga kota lain, derajatnya adalah $3$.

Lintasan

Lintasan adalah urutan simpul di mana setiap pasangan berurutan terhubung oleh sebuah sisi.

Jika ada lintasan dari satu simpul ke simpul lain, Anda dapat berpindah dari satu ke yang lain dengan mengikuti sisi-sisinya.

Siklus

Siklus adalah lintasan yang dimulai dan berakhir pada simpul yang sama. Dalam definisi dasar yang umum, tidak ada simpul lain yang diulang.

Siklus menunjukkan bahwa ada loop tertutup dalam graf.

Graf terhubung dan komponen terhubung

Sebuah graf tak berarah disebut terhubung jika setiap simpul dapat dicapai dari setiap simpul lain melalui suatu lintasan.

Jika hal itu tidak terpenuhi, graf akan terpecah menjadi komponen terhubung. Setiap komponen adalah bagian graf yang terhubung.

Contoh Dikerjakan: Satu Graf Kecil

Misalkan sebuah graf memiliki simpul $A$, $B$, $C$, $D$, dan $E$, dengan sisi

$$AB,\ AC,\ BC,\ CD$$

Ini membentuk sebuah segitiga pada $A$, $B$, dan $C$, satu sisi tambahan dari $C$ ke $D$, dan satu simpul terisolasi $E$.

Sekarang gagasan utamanya mudah dilihat.

Derajatnya adalah

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Ada lintasan dari $A$ ke $D$:

$$A-C-D$$

Ada sebuah siklus:

$$A-B-C-A$$

Graf ini tidak terhubung karena $E$ tidak dapat dicapai dari simpul-simpul lainnya. Jadi graf ini memiliki dua komponen terhubung: satu yang memuat $A,B,C,D$ dan satu lagi yang hanya memuat $E$.

Contoh tunggal ini menunjukkan bagaimana derajat, lintasan, siklus, simpul terisolasi, dan komponen terhubung saling berkaitan.

Pemeriksaan Cepat: Jumlah Derajat

Untuk setiap graf tak berarah berhingga,

$$\sum \deg(v) = 2|E|$$

Ini berlaku karena setiap sisi menyentuh tepat dua titik ujung, sehingga setiap sisi menambahkan $1$ pada dua hitungan derajat.

Pada contoh di atas, jumlah derajatnya adalah

$$2+2+3+1+0=8$$

dan banyak sisi adalah $4$, sehingga

$$2|E| = 2 \cdot 4 = 8$$

Ini adalah pemeriksaan yang berguna saat Anda menghitung derajat secara manual. Jika angkanya tidak cocok, berarti ada yang salah.

Kesalahan Umum dalam Teori Graf

Mencampuradukkan simpul dan sisi

Simpul adalah objeknya. Sisi adalah hubungan di antaranya.

Lupa jenis graf yang sedang digunakan

Pernyataan yang benar untuk graf sederhana tak berarah mungkin perlu diubah untuk graf berarah atau untuk graf yang mengizinkan loop.

Menganggap lintasan sama seperti siklus

Lintasan tidak harus kembali ke titik awalnya. Siklus harus kembali.

Mengabaikan simpul terisolasi

Simpul dengan derajat $0$ tetap merupakan bagian dari graf. Simpul itu dapat mengubah apakah graf tersebut terhubung atau tidak.

Di Mana Dasar-Dasar Teori Graf Digunakan

Gagasan-gagasan ini muncul dalam jaringan komputer, perencanaan rute, penjadwalan, sistem rekomendasi, dan jejaring sosial. Konteksnya berubah, tetapi pertanyaan yang sama terus muncul: apa yang terhubung, apa yang dapat dicapai, dan di mana loop berada?

Itulah sebabnya teori graf muncul sejak awal dalam matematika diskrit maupun ilmu komputer.

Coba Graf Serupa

Gambarlah empat simpul $P$, $Q$, $R$, dan $S$. Tambahkan sisi $PQ$, $QR$, $RS$, dan $SP$.

Lalu jawab tiga pertanyaan: berapa derajat setiap simpul, apakah graf tersebut terhubung, dan apakah graf tersebut mengandung sebuah siklus?