Graph

    GraphDinyatakan dalam suatu fungsi G = (V , E ) dim anaV = kum pulan sim pul/ vertex/ nodeE = kum pulan busur / edge/ arcTiap busur pasti menghubungkan 2 simpul. Ada 2 macam graph1. Graph tak terarah (Undirected graph)2. Graph terarah (Directed graph)
Pengertian Graf PerbedaannyaGraf adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual darigraph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).
G = (V, E)DimanaG = GraphV = Simpul atau Vertex, atau Node, atau TitikE = Busur atau Edge, atau arcGraf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut.

Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memmanipulasi graph. Secara teori salah satu dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya.

• Graph tak berarah (undirected graph atau non-directed graph) :• Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB atau BA• Graph berarah (directed graph) :• Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.• Graph Berbobot (Weighted Graph)• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

Adapun Perbedaan Graph dengan Tree sebagai berikut:a. Pada Tree tidak terdapat Cycleb. Pada Graph tidak memiliki root

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau (directed graph). Digraf dengan sisi berbobot disebut jaringan.
Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah




Pada digraf maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut :

Dalam himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari edge tersebut.
Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :

• Degree
 atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.

• Path
 suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path 

• Cycle
 siklus ? path yang kembali melalui titik asal 2  kembali ke 2.

• Tree
 merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf di atas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex

• Graf Tak Berarah (Undirected Graph)
 Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (v_i,v_j)=(v_j,v_i)

• Graf Berarah (Directed Graph)
 Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.

graph untitled {
        graph[bgcolor="transparent"];
        node [fontname="Bitstream Vera Sans", fontsize="22.00", shape=circle, style="bold,filled" fillcolor=white];
        edge [style=bold];
        1;2;3;4;5;6;
        6 -- 4 -- 5 -- 1 -- 2 -- 3 -- 4;
        2 -- 5;
}