GRAPH

Graph
Suatu graph mempunyai 2 himpunan, yaitu :
Himpunan V yang elemennya disebut simpul (Vertex atau Point atau Node atau Titik)
Himpunan E yang merupakan pasangan tak urut dari simpul. Anggotanya disebut Ruas (Edge atau rusuk atau sisi)
Graph seperti dimaksud diatas, ditulis sebagai sebagai G(E,V).
Banyak simpul (vertex) disebut Order, sedangkan banyaknya ruas (edge) disebut Size dari graph.
Graph sederhana atau simple graph : Suatu graph yang tidak mengandung ruas sejajar ataupun self-loop.
Graph Berlabel
Graph G disebut berlabel jika ruas dan atau simpulnya dikaitkan dengan suatu besaran tertentu.
Derajat Graph
Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu Graph.
Bila jumlah derajat semua simpul sama dengan genap, maka disebut EULER GRAPH.

KETERHUBUNGAN
Walk atau perjalanan dalam graph G adalah barisan simpul dan ruas berganti-ganti : V1,e1,V2,e2,……,e n-1,Vn
Disini ruas ei menghubungkan simpul Vi dan Vi+1.
Banyaknya ruas disebut Panjang Walk.
Walk disebut terbuka, yang menghubungkan V1 dan Vn, yaitu setiap ruas menghubungkan Simpul Awal dan Akhir.
Trail adalah Walk dengan semua ruas dalam barisan adalah berbeda.
Path atau jalur adalah Walk yang semua simpul dalam barisan adalah berbeda. Jadi suatu Path pastilah sebuah Trail.
Cycle atau sirkuit adalah suatu trail tertutup dengan derajat setiap simpul =2. Cycle dengan panjang k disebut dengan k-cycle. Demikian pula jalur dengan panjang k disebut k-jalur.
Grap yang tidak mengandung Cycle disebut Acyclic.
Contoh dari Graph Acyclic adalah pohon atau Tree.
Subgraph yang terhubung pada suatu Graph disebut komponen dari G bila Subgraph tersebut tidak terkandung dalam Subgraph terhubung lain yang lebih besar.