Apa itu Graf, matriks ketetanggaan?

Suatu graf terdiri atas simpul $1, 2, \dots, n$ dan sisi yang menghubungkan pasangan simpul tertentu (pasangan terurut bagi graf berarah). Matriks ketetanggaan dari graf itu adalah matriks $n \times n$ bernama $M$ dengan $m_{ij} = 1$ jika ada sisi dari $i$ ke $j$, dan $0$ jika tidak. Suatu jalan sepanjang $k$ dari $i$ ke $j$ adalah barisan $k$ sisi berturut-turut yang membawa dari $i$ ke $j$.