Graf (matematika)

Dalam matematika diskrit, khususnya teori graf, graf merupakan suatu struktur yang terdiri dari beberapa objek dan hubungan antar pasangan objek-objek tersebut. Secara sederhana, sebuah graf merupakan himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang memenuhi syarat, di mana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (simpul) yang dihubungkan dengan sisi.

Sebuah graf dengan 6 sudut dan 7 sisi.

Definisi

Graf memiliki definisi yang bervariasi. Di bawah ini merupakan definisi dasar graf dan strukturnya.

Graf

Sebuah graf (tidak berarah) $G$ adalah sebuah pasangan $G:=(V,E)$ dengan $V$ adalah sebuah himpunan tak kosong beranggotakan titik atau simpul dan $E$ adalah sebuah himpunan beranggotakan sisi, yakni pasangan titik. Misalkan $u$ dan $v$ adalah titik pada graf, sisi yang menghubungkan $u$ dan $v$ biasa ditulis sebagai $uv$.

Jika sisi $uv$ adalah anggota himpunan $E$, sisi $u$ dan $v$ disebut bertetangga. Untuk suatu titik pada graf, lingkungan titik tersebut adalah himpunan seluruh titik yang bertetangga dengannya. Derajat dari suatu titik adalah banyak sisi yang terkait dengan titik tersebut.