Implementasi dalam struktur data

Walau secara konseptual struktur linear adalah subset dari tree dan demikian pula tree adalah subset dari graph, dalam aplikasinya perlu dibedakan cara penanganan struktur-struktur tersebut untuk mencapai efisiensi algoritmis. Algoritma-algoritma untuk graph secara umum terlalu mahal apabila digunakan pada struktur hirarkis (tree), apalagi pada struktur linear. Jadi apabila masalah yang dihadapi pada dasarnya hanya merupakan masalah dengan struktur data hirarkis saja maka cukup lah kita menggunakan representasi dan algoritma-algoritma tree.
Konektivitas pada Undigraph

* Adjacency: Dua verteks x dan y yang berlainan disebut berhubungan langsung (adjacent) jika terdapat sisi {x, y} dalam E.
* Path: Sederetan verteks yang mana setiap verteks adjacent dengan verteks yang tepat berada disebelahnya.
* Panjang dari path: jumlah sisi yang dilalui path.
* Siklus: suatu path dengan panjang lebih dari satu yang dimulai dan berakhir pada suatu verteks yang sama.
* Siklus sederhana: dalan undigraph, siklus yang terbentuk pada tiga atau lebih verteks-verteks yang berlainan yang mana tidak ada verteks yang dikunjungi lebih dari satu kali kecuali verteks awal/akhir.
* Dua verteks x dan y yang berbeda dalam suatu undigraph disebut berkoneksi (connected) apabila jika terdapat path yang menghubungkannya.
* Himpunan bagian verteks S disebut terkoneksi (connected) apabila dari setiap verteks x dalam S terdapat path ke setiap verteks y (y bukan x) dalam S.
* Suatu komponen terkoneksi (connected components) adalah subgraph (bagian dari graph) yang berisikan satu himpunan bagian verteks yang berkoneksi.
* Suatu undigraph dapat terbagi atas beberapa komponen yang terkoneksi; jika terdapat lebih dari satu komponen terkoneksi maka tidak terdapat path dari suatu verteks dalam satu komponen verteks di komponen lainnya.
* Pohon bebas (free tree): suatu undigraph yang hanya terdapat satu komponen terkoneksi serta tidak memiliki siklus sederhana.

Konektivitas pada Digraph

Terminologi di atas berlaku juga pada Digraph kecuali dalam digraph harus dikaitkan dengan arah tertentu karena pada arah yang sebaliknya belum tentu terdefinisi.

* Adjacency ke / dari: Jika terdapat sisi (x,y) maka dalam digraph dikatakan bahwa x "adjacent ke" y atau y "adjacent dari" x. Demikian pula jika terdapat path dari x ke y maka belum tentu ada path dari y ke x Jadi dalam digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.
* Terkoneksi dengan kuat: Himpunan bagian verteks S dikatakan terkoneksi dengan kuat (strongly connected) bila setiap pasangan verteks berbeda x dan y dalam S, x berkoneksi dengan y dan y berkoneksi dengan x (dpl., ada path dari x ke y dan sebaliknya dari y ke x).
* Terkoneksi dengan Lemah: Himpunan bagian verteks S dikatakan terkoneksi dengan lemah (weakly connected) bila setiap pasangan verteks berbeda x dan y dalam S, salah satu: x berkoneksi dengan y (atau y berkoneksi dengan x) dan tidak kebalikan arahnya (dpl., hanya terdefinisi satu path: dari x ke y atau sebaliknya dari y ke x).

Himpunan Keterhubungan Langsung

Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal:
Vx = {y | (x,y) Î E}

Dalam digraph didefinisikan juga terminologi-terminologi berikut ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang adjacent dari x; yaitu adjacency set di atas. .