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) ${\displaystyle G}$ adalah sebuah pasangan ${\displaystyle G:=(V,E)}$ dengan ${\displaystyle V}$ adalah sebuah himpunan tak kosong beranggotakan titik^[1] atau simpul^[2] dan ${\displaystyle E}$ adalah sebuah himpunan beranggotakan sisi, yakni pasangan titik. Misalkan ${\displaystyle u}$ dan ${\displaystyle v}$ adalah titik pada graf, sisi yang menghubungkan ${\displaystyle u}$ dan ${\displaystyle v}$ biasa ditulis sebagai ${\displaystyle uv}$.^[3]

Jika sisi ${\displaystyle uv}$ adalah anggota himpunan ${\displaystyle E}$, sisi ${\displaystyle u}$ dan ${\displaystyle 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.^[4]

Referensi

1. Marsudi (2016-12-05). Teori Graf. Universitas Brawijaya Press. ISBN 978-602-432-015-7. Diarsipkan dari versi asli tanggal 2023-08-08. Diakses tanggal 2022-10-29.
2. Rinaldi Munir (2010). Matematika Diskrit. Bandung: Informatika. Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
3. Aisyah, Putri Wahyu; Narwen, Narwen; Zulakmal, Zulakmal (2019-02-19). "Menentukan Bilangan Kromatik Lokasi Pada Graf Berlapis Cn,2n,2n". Jurnal Matematika UNAND. 7 (3): 136–143. doi:10.25077/jmu.7.3.136-143.2018. ISSN 2721-9410.
4. Syafrizal Sy; Edy Tri Baskoro (2022-04-08). Surahmat, ed. Bilangan Ramsey Multipartit Ukuran. Padang: Universitas Andalas. ISBN 978-623-395-211-8. Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)