Graf (matematika)

Graf tidak berarah

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, atau busur^[3] 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}$.^[4]

Sisi atau busur dapat memiliki bobot. Pada graf dengan sisi yang memiliki bobot, graf dapat ditulis sebagai ${\displaystyle G:=(V,E,W)}$, di mana W adalah fungsi bobot.^[3]

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

Graf berarah

Suatu busur (sisi) ${\displaystyle uv}$ disebut sebagai busur berarah jika terdapat aliran dari simpul ${\displaystyle u}$ ke simpul ${\displaystyle v}$. Simpul ${\displaystyle u}$ disebut sebagai simpul pangkal (simpul awal) dan simpul ${\displaystyle v}$ sebagai simpul akhir (simpul ujung) dari sisi ${\displaystyle uv}$. Bila terdapat busur berarah ${\displaystyle uv}$ dan ${\displaystyle vu}$ busur itu disebut sebagai busur dua arah. Suatu graf ${\displaystyle G}$ disebut sebagai graf berarah jika semua busur pada graf tersebut berarah.^[6]