GRAPH

Teori graph merupakan salah satu bagian yang paling penting dalam matematika kombinatorial. Pada teori graph diberikan model matematika untuk setiap himpunan dari sejumlah objek diskrit, dimana beberapa pasangan unsure dari himpunan tersebut terikat menurut suatu aturan tertentu. Objek diskrit dari himpunan tersebut dapat berupa orang-orang yang memenuhi aturan tertentu, misalnya aturan kenal. Objek dapat juga berupa suatu himpunan nama kota dengan aturan jalan yang menghubungkan antara kota satu ke kota yang lain. Makalah pertama tentang teori graph ditulis oleh seorang ahli matematika dari Swiss Leonard Euler pada tahun 1736 yang berisi persoalan jembatan Konigsberg. Cikal bakal dari teori graph dinyatakan dalam bentuk permainan atau teka-teki. Tetapi sekarang ini teori graph telah dapat memberikan kerangka dasar bagi banyak persoalan yang berhubungan dengan struktur dan hubungan antara suatu objek diskrit dalam bentuk apapun. Pemakaian teori graph telah dapat diterapkan dalam berbagai cabang ilmu pengetahuan seperti ekonomi, psikologi, ilmu sosial, genetika, riset operasional dan lain sebagainya.

Defenisi Graph
Sebuah graph G berisikan dua himpunan yaitu himpunan berhingga tak kosong V(G) dari obyek-obyek yang disebut titik (vertex) dan himpunan berhingga (mungkin kosong) E(G) yang elemen-elemennya disebut sisi (edge) sedemikian hingga setiap elemen e dalam E(G) merupakan pasangan tak berurutan dari titik-titik di V(G). Himpunan V(G) disebut himpunan titik G, dan himpunan E(G) disebut himpunan sisi G.
Sebuah graph G dapat dipresentasikan dalam bentuk diagram (gambar) dimana setiap titik G digambarkan dengan sebuh noktah dan setiap sisi yang menghubungkan dua titik di G digambarkan dengan sebuah kurva sederhana (ruas garis) dengan titik-titik akhir di kedua titik tersebut.
Sebuah sisi graph yang menghubungkan sebuah titik dengan dirinya sendiri disebut gelung (loop). Jika terdapat lebih dari satu sisi yang menghubungkan dua titik u dan v pada suatu graph, maka sisi-sisi tersebut disebut sisi-rangkap/sisi-ganda (multiple-edges).


Sumber :http://www.konsep-konsep-dasar-teori-graph.html