Dalam bagian ini, kita memperkenalkan varian graf lain yang berguna. Dalam graf, keberadaan sisi \(xy\) dapat digunakan untuk memodelkan hubungan dua arah antara \(x\) dan \(y\text{.}\) Namun, kadang-kadang model semacam itu tidak memadai. Sebagai contoh, mungkin tersedia penerbangan langsung dari Atlanta ke Fargo, tetapi tidak tersedia penerbangan langsung dari Fargo ke Atlanta. Dalam graf yang merepresentasikan jaringan penerbangan, sisi antara Atlanta dan Fargo akan menghilangkan informasi bahwa penerbangan hanya beroperasi dalam satu arah. Untuk menangani persoalan ini, kita memperkenalkan struktur diskret baru. Sebuah digraf \(\bfG\) adalah pasangan \((V,E)\text{,}\) dengan \(V\) himpunan simpul dan \(E\subset V\times V\text{,}\) serta \(x\neq y\) untuk setiap \((x,y)\in E\text{.}\) Kita memandang pasangan \((x,y)\) sebagai sisi berarah dari \(x\) ke \(y\text{.}\) Perhatikan bahwa untuk simpul-simpul berbeda \(x\) dan \(y\) dalam \(V\text{,}\) pasangan terurut \((x,y)\) dan \((y,x)\) berbeda. Jadi, digraf dapat mempunyai salah satu, keduanya, atau tidak satu pun dari sisi berarah \((x,y)\) dan \((y,x)\text{.}\) Hal ini berbeda dari graf biasa, yang sisinya berupa himpunan, sehingga \(\{x,y\}\) dan \(\{y,x\}\) sama.
Diagram digraf menggunakan ujung panah pada sisi untuk menunjukkan arah, seperti diperlihatkan dalam Gambar 12.12. Sebagai contoh, digraf pada gambar tersebut memuat sisi \((a,f)\text{,}\) tetapi tidak memuat sisi \((f,a)\text{.}\) Namun, digraf itu memuat kedua sisi \((c,d)\) dan \((d,c)\text{.}\)
Jika \(\bfG\) merupakan digraf, barisan simpul berbeda \(P=(r=u_0,u_1,\dots,u_t=x)\) disebut lintasan berarah dari \(r\) ke \(x\) apabila \((u_i,u_{i+1})\) merupakan sisi berarah dalam \(\bfG\) untuk setiap \(i=0,1,\dots,t-1\text{.}\) Lintasan berarah \(C=(r=u_0,u_1,\dots,u_t=x)\) disebut siklus berarah apabila \((u_t,u_0)\) merupakan sisi berarah dalam \(\bfG\text{.}\)
