Graf adalah salah satu cabang dari keilmuan Struktur Diskrit yang sudah sangat tua umurnyadan memiliki banyak aplikasi dalam kehidupan sehari-hari. Bila graf dimisalkan dengan G maka graf G didefinisikan sebagai pasangan himpunan (V, E) yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau nodes), sedangakn E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. Notasi graf dapat disingkat menjadi G(V, E).
Graf memiliki banyak jenis, terminologi, dan penerapan. Beberapa dari jenis dan terminologi yang akan dibahas dalam artikel ini antara lain graf terhubung, graf berbobot, lintasan dan sirkuit Hamilton, serta lintasan dan sirkuit Euler.
Graf terhubung adalah graf dimana graf tak-berarahnya terhubung, dimana dua buah simpul vi dan vj dikatakan terhubung bila terdapat lintasan dari vi ke vj yang mengubungkan kedua simpul tersebut. Graf berbobot (weighted graph) adalah graf yang setiap sisinya diberi harga (bobot). Lintasan Hamilton adalah lintsasan yang melalui setiap simpul dalam graf tepat satu kali dan bila lintasan itu kembali ke simpul asal memebntuk lintasan tertutup (sirkuit), maka lintasan itu disebut sirkuit Hamilton. Sedangkan lintasan Euler adalah lintasan yang melalui setiap sisi dalam graf tepat satu kali dan bila lintasan itu kembali ke simpul asal, membentuk sirkuit maka disebut sirkuit Euler.
 |
| teori-graf-pohon gambar : (a) bukan pohon, gambar (b) pohon |
Konsep pohon (tree) mungkin adalah konsep yang paling penting dari sekian banyak konsep dari teori graf. Pohon didefinisikan sebagai graf terhubung yang tidak memiliki sirkuit. Pohon dapat dibagi menjadi dua yaitu pohon bebas (free tree) dan pohon berakar (rooted tree). Dari sekian banyak konsep, teori, dan penerapan yang ada dalam pohon, yang akan dibahas dalam artikel ini antara lain adalah konsep pohon berakar. Pohon berakar adalah pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah sehingga menjadi graf berarah.
 |
| pohon-berakar-graf gambar : (a)pohon berkar (b)pohon berakar, dengan arah panah dibuang |
