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 atau busur. 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.

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

 Graf tidak berarah 
Sebuah graf (tidak berarah)  adalah sebuah pasangan  dengan  adalah sebuah himpunan tak kosong beranggotakan titik atau simpul dan  adalah sebuah himpunan beranggotakan sisi, atau busur yakni pasangan titik. Misalkan  dan  adalah titik pada graf, sisi yang menghubungkan  dan  biasa ditulis sebagai .

Sisi atau busur dapat memiliki bobot. Pada graf dengan sisi yang memiliki bobot, graf dapat ditulis sebagai , di mana W adalah fungsi bobot.

Jika sisi  adalah anggota himpunan , titik  dan  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.

 Graf berarah 
Suatu busur (sisi)  disebut sebagai busur berarah jika terdapat aliran dari simpul  ke simpul . Simpul  disebut sebagai simpul pangkal (simpul awal) dan simpul  sebagai simpul akhir (simpul ujung) dari sisi . Bila terdapat busur berarah  dan  busur itu disebut sebagai busur dua arah. Suatu graf  disebut sebagai graf berarah jika semua busur pada graf tersebut berarah.

 Referensi 

Kategori:Teori graf