TEORI GRAPH

TUGAS TERSTRUKTUR

TEORI GRAPH

“Sejarah Lahirnya Teori Graph dan Pemodelan Dalam Graph”

Dosen Pengampuh:
Rini Warti, S.Si, M.Si

Dibuat Oleh:
kelompok 9

1.      Puryanti                    : TM100662

2.      Rahmat Firdaus        : TM100664

3.      Rita Agustiana Sari  : TM100670

4.      Ulfa Husna               : TM100687

Jurusan

Tadris Matematika

IAIN STS JAMBI

2013

BAB 1
PENDAHULUAN

A.    SEJARAH LAHIRNYA TEORI GRAPH

Teori graph lahir pada Tahun 1736 melalui tulisan Leonhard Euler yang berisi tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa. Permasalahannya adalah " Apakah bisa seseorang  melalui  sekali setiap jembatan yang menghubungkan kota-kota tersebut, dan kembali lagi ke kota dari mana ia berjalan".

Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya-genap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh, simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakukan perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.

Kurang lebih seratus tahun setelah lahirnya tulisan Euler tersebut tidak ada perkembangan yang berarti berkenaan dengan teori graph.  Tahun 1847, G.R. Kirchoff (1824 – 1887) berhasil mengembangkan teori pohon (Theory of trees) yang digunakan dalam persoalan jaringan listrik. Sepuluh tahun kemudian, A. Coyley (1821 – 1895) juga menggunakan konsep pohon untuk menjelaskan permasalahan kimia yaitu hidrokarbon. Pada masa Kirchoff dan Coyley juga telah lahir dua hal penting dalam teori graph. Salah satunya berkenaan dengan konjektur empat warna, yang menyatakan bahwa untuk mewarnai sebuah atlas cukup dengan menggunakan empat macam warna sedemikian hingga tiap negara yang berbatasan akan memiliki warna yang berbeda.

Para ahli teori graph berkeyakinan bahwa orang yang pertama kali mengemukakan masalah empat warna adalah A.F. Mobius (1790 – 1868) dalam salah satu kuliahnya di Tahun 1840. Sepuluh tahun kemudian, A. De Morgan (1806 – 1871) kembali membahas masalah ini bersama ahli-ahli matematika lainnya di kota London. Dengan demikian tulisan De Morgan dianggap sebagai referensi pertama berkenaan dengan masalah empat warna. Masalah empat warna ini menjadi sangat terkenal setelah Coyley mempublikasikannya pada tahun 1879 dalam “Proceedings of the Royal Geographic Society” volume pertama. Hal lain yang penting untuk dibicarakan sehubungan dengan perkembangan teori graph adalah apa yang dikemukakan oleh Sir W.R. Hamilton (1805 – 1865). Pada Tahun 1859 dia berhasil menemukan suatu permainan yang kemudian dijualnya ke sebuah pabrik mainan di Dublin. Permainan tersebut terbuat dari kayu berbentuk dodecahedron beraturan yakni berupa sebuah polihedron dengan 12 muka dan 20 pojok. Tiap muka berbentuk sebuah pentagon beraturan dan tiap pojoknya dibentuk oleh tiga sisi berbeda. Tiap pojok dari dodecahedron tersebut dipasangkan dengan sebuah kota terkenal seperti London, New York, Paris, dan lain-lain. Masalah dalam permainan ini adalah, kita diminta untuk mencari suatu rute melalui sisi-sisi dari dodecahedron sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali. Walaupun saat ini masalah tersebut dapat dikategorikan mudah, akan tetapi pada saat itu tidak ada seorang pun yang bisa menemukan syarat perlu dan cukup dari eksistensi rute yang dicari.

Kurang lebih setengah abad setelah masa Hamilton, aktivitas dalam bidang teori graph dapat dikatakan relatif kecil. Pada Tahun 1920-an kegiatan tersebut muncul kembali yang dipelopori oleh D. Konig. Konig berupaya mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graph termasuk hasil pemikirannya sendiri, kemudian dikemasnya dalam bentuk buku yang diterbitkan pada Tahun 1936. Buku tersebut dianggap sebagai buku pertama tentang teori graph.

Tiga puluh tahun terakhir ini merupakan periode yang sangat intensif dalam aktivitas pengembangan teori graph baik murni maupun terapan. Sejumlah besar penelitian telah dilakukan, ribuan artikel telah diterbitkan dan lusinan buku telah banyak ditulis. Di antara orang terkenal yang banyak berkecimpung dalam bidang ini adalah Claude Berge, Oysten Ore, Paul Erdos, William Tutte, dan Frank Harary.

B.     PEMODELAN DALAM GRAPH

1.      Rangkaian listrik.

Kirchoff (1847) menggunakan graf untuk memodelkan rangkaian listrik. Berdasarkan graf tersebut, Kirchoff menurunkan persamaan arus yang masuk dan keluar pada tiap simpul. Dari sistem persamaan lanjar (linier) simultan yang diperoleh dapat dihitung arus listrik yang mengalir pada setiap komponen.

Gambar 4.1 (a) Rangkaian listrik, (b) graf yang menyatakan rangkaian listrik

2.      Isomer senyawa kimia karbon

Arthur Cayley (1857) menggunakan graf dalam memodelkan molekul senyawa alkana CnH_2n+2 untuk menghitung jumlah isomernya. Atom karbon (C) dan atom hidrogen (H) dinyatakan sebagai simpul, sedangkan ikatan antara atom C dan H dinyatakan sebagai sisi (Gambar 8.7). Isomer adalah senyawa kimia yang mempunyai rumus molekul sama tetapi rumus bangun (bentuk graf) berbeda.

Gambar 4.2 Graf senyawa alkana, masing-masing metana, etana, dan propane

3.      Transaksi konkuren pada basis data terpusat

Ini adalah terapan graf dalam bidang komputer. Basis data (database) terpusat melayani beberapa transaksi (T) yang dilakukan secara konkuren (bersamaan). Transaksi terhadap basis data dapat berupa operasi pembacaan dan operasi penulisan terhadap data yang sama. Persoalan kritis pada proses konkuren adalah deadlock, yaitu keadaan yang timbul karena beberapa transaksi saling menunggu transaksi lainnya sehingga sistem menjadi hang. Misalnya, transaksi T1 akan membaca data B yang sedang ditulis oleh transaksi T2, sedangkan T2 akan membaca data A yang sedang ditulis T1. Kedua transaksi saling menunggu data yang sedang dikuncinya (circular wait). Bila terdapat lebih dari dua transaksi yang saling menunggu sehingga membentuk siklus, maka timbul deadlock. Cara yang digunakan sistem untuk mendeteksi deadlock adalah dengan membangun graf transaksi secara periodik dan memeriksa apakah terdapat siklus pada grafnya. Jika ada siklus, maka kondisi deadlock terjadi . Misalkan:

transaksi T0 menunggu transaksi T1 dan T2 ;

transaksi T2 menunggu transaksi T1 ;

transaksi T1 menunggu transaksi T3 ;

transaksi T3 menunggu transaksi T2 ;

Graf berarah yang menyatakan transaksi menunggu transaksi lainnya ditunjukkan pada Gambar 8.8. Simpul menyatakan transaksi, sedangkan busur (Ti, Tj) menyatakan transaksi Ti menunggu transaksi Tj. Graf ini mengandung siklus, yaitu T1 - T3 - T2 - T1 Untuk mengatasi deadlock, sistem harus memutuskan siklus dengan cara membatalkan satu atau lebih transaksi di dalam siklus. Metode penanganan deadlock tidak dibahas di dalam buku ini, karena merupakan bagian dari kuliah Sistem Operasi dan Sistem Basis Data.

Gambar 4.3 Graf transaksi yang menunjukkan keadaan deadlock

4.      Pengujian program

Dalam bidang rekayasa perangkat lunak, sebuah program harus mengalami tahap pengujian untuk menemukan kesalahan (bug). Salah satu pengujian program adalah pengujian eksekusi. Aliran kendali program harus diperiksa untuk memastikan apakah aliran tersebut sudah benar untuk berbagai kasus data uji. Aliran kendali program dimodelkan dengan graf berarah yang dinamakan graf alir (flow graph). Pada graf berarah tersebut, simpul menyatakan pernyataan atau kondisi yang dievaluasi, sedangkan busur menyatakan aliran kendali program ke pernyataan atau kondisi berikutnya. Sebagai contoh, misalkan terdapat sebagian teks program Pascal di bawah ini:

Gambar 4.4

Gambar 4.5 Graf alir yang menggambarkan aliran kendali program

Data pengujian harus dirancang sedemikian sehingga semua lintasan di dalam graf alir pernah dilalui minimum satu kali. Tujuannya agar kesalahan pada setiap lintasan eksekusi dapat ditemukan dan perbaikan program dilakukan.

5.      Terapan graf di dalam teori otomata [LIU85].

Marilah kita simak masalah pemodelan perilaku sebuah mesin jaja (vending machine) yang menjual coklat seharga 15 sen sebuah. Untuk memudahkan, kita akan memisalkan bahwa mesin tersebut hanya menerima uang logam 5 sen dan 10 sen, dan mesin tidak akan memberi kembalian bila yang dimasukkan lebih dari 15 sen. Graf berbobot (setiap sisi diberi sebuah harga, akan diejlaskan kemudian)

Gambar 4.6 Graf yang memodelkan perilaku mesin jaja

6.      Turnamen Round-Robin

Turnamen yang setiap tim bertanding dengan tim lainnya hanya sekali disebut turnamen round-robin. Turnamen semacam itu dimodelkan dengan graf berarah, yang dalam hal ini simpul menyatakan tiap tim yang bertanding, dan busur menyatakan pertandingan. Busur (a, b) berarti tim a berhasil memukul tim b. Gambar 4.7 memperlihatkan turnamen round-robin untuk 6 buah tim. Tim 1 tidak terkalahkan, sedangkan tim 3 tidak pernah menang.

Gambar 4.7 Turnamen round-robin

Contoh terapan graf yang lain adalah menyatakan aliran informasi dalam pengolahan sinyal dan aliran massa dalam industri kimia. Graf juga berguna memodelkan sesuatu yang abstrak, seperti struktur perusahaan, tingkatan sosial, pohon keluarga, aliran kerja dalam proyek, perencanaan dan manajemen proyek, perpindahan dalam permainan (game), dan langkah-langkah pemecahan masalah. Terapan yang terakhir ini merupakan kemampuan dasar yang harus dikuasai dalam bidang kecerdasan buatan (artificial intelligence).

Model Graf

Contoh 1:

Bagaimana cara merepresentasikan jaringan (dua arah) KA yang menghubungkan sekumpulan kota?

Kita harus memakai graf sederhana dengan garis hubung {a, b} merupakan jalur langsung yang menghubungkan kota a dengan kota b.

KONSEP-KONSEP DASAR TEORI GRAPH

KONSEP-KONSEP DASAR TEORI GRAPH

A. Pendahuluan

 

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.

B. 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).

C. Jenis-jenis Graph
1. Graph sederhana
Graph yang tidak mempunyai sisi rangkap dan tidak memiliki gelung disebut graph sederhana.
2. Graph tidak sederhana
a. Graph rangkap
Sebuah graph yang memiliki sisi rangkap tetapi tidak memiliki gelung disebut graph rangkap (multi-graph).
b. Graph semu
Sebuah graph yang memilki sisi rangkap dan memiliki gelung disebut graph semu (pseudograph).
3. Graph komplit
Sebuah graph komplit (graph lengkap) dengan n titik, dilambangkan dengan Kn , adalah graph sederhana dengan n titik dan setiap dua titik berbeda dihubungkan dengan sebuah sisi.
Sebuah graph lengkap sering juga disebut sebagai graph universal. Kerena tiap titik dalam grap lengkap selalu dihubungkan dengan titik lain melalui satu sisi, maka derajat tiap titik dalam sebuah graph lengkap G dengan n titik adalah n-1. Dengan demikian, banyaknya sisi dalam graph lengkap G adalah .
4. Graph bagian (subgraph)
Sebuah graph H disebut graph bagian (subgraph) dari graph G
5. Graph teratur
Sebuah graph disebut graph teratur jika semua titiknya berderajat sama. Misal graph teratur berderajat tiga.
6. Graph lingkaran
Graph sederhana yang setiap titiknya berderajat dua disebut graph lingkaran. Graph lingkaran dengan n titik dilambangkan dengan Cn. Graph lingkaran ini disebut juga graph teratur berderajat dua.
7. Graph kosong atau graph nol
Graph yang tidak memiliki sisi disebut graph kosong atau graph nol. Graph nol dengan n titik dilambangkan dengan Nn. Graph yang hanya mempunyai satu buah titik tanpa sebuah sisi dinamakan graph trivial. Misal graph kosong dengan tiga titik (N3).
8. Graph bipartisi
Sebuah graph G disebut graph bipartisi jika V(G) (himpunan titik graph G) dapat dipartisi menjadi dua himpunan bagian X dan Y sedemikian sehingga setiap sisi dari G menghubungkan sebuah titik di X dan sebuah titik di Y. Kita notasikan (X,Y) bipartisi dari G.
Apabila G sederhana dan bipartisi dengan partisi (X,Y) sedemikian sehingga setiap titik di X berhubungan langsung dengan setiap titik di Y, maka G disebut graf bipartisi lengkap, dinotasikan dengan Km,n dengan m dan n adalah banyaknya titik dikedua partisi tersebut.
9. Graph berbobot
Sebuah graph G disebut graph berbobot jika setiap sisinya diberi sebuah harga.
D. Terminologi (Istilah) Dasar Pada Graph
1. Bertetangga (adjacent)
Dua buah titik, titik u dan titik v pada graph tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, u bertetangga dengan v jika (u,v) adalah sebuah sisi pada graph G.
2. Bersisian (incident)
Misal sembarang sisi , sisi e dikatakan bersisian dengan titik u dan titik v.
3. Titik terpencil (isolated vertex)
Titik terpencil adalah titik yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dikatakan bahwa titik terpencil adalah titik yang tidak satupun bertetangga dengan titik-titik lainnya.
4. Jalan (walk)
Misalkan G adalah sebuah graph. Sebuah jalan (walk) di G adalah sebuah barisan berhingga (tak kosong) yang suku-sukunya bergantian titik dan sisi, sedemikian hingga dan adalah titik-titik akhir sisi ei, untuk . Katakan W adalah sebuah jalan dari titik (titik awal) ke titik (titik akhir), sedangkan titik-titik disebut titik-titik internal W dan k disebut panjang jalan W. Dengan kata lain, jalan (walk) ialah dimana sisi dan titiknya boleh berulang.
Dari gambar, barisan adalah sebuah jalan di graph G yang panjangnya 4.
5. Jejak (trail)
Jejak adalah jalan yang sisi-sisinya tidak ada yang sama, tetapi titiknya boleh ada yang sama.
Dari gambar, barisan adalah sebuah jejak di graph G dengan panjang 5.
6. Lintasan (path)
Lintasan adalah jejak yang semua titiknya berbeda (sisi dan titiknya tidak ada yang sama).
Dari gambar, barisan adalah sebuah lintasan di graph G dengan panjang 4.
7. Sirkit
Sirkit adalah Jejak tertutup.
Dari gambar, barisan adalah sebuah jejak tertutup (sirkit) di graph G dengan panjang 8.
8. Siklus/lintasan tertutup (sikel)
Sikel adalah sebuah sirkit yang titik awal dan semua titik internalnya berbeda (titik awal dan titik akhirnya sama dimana titik dan sisinya tidak ada yang berulang).
Dari gambar, barisan adalah sebuah sikel di graph G dengan panjang 4.
9. Terhubung dan tidak terhubung
Suatu graph G dikatakan terhubung jika dan hanya jika setiap 2 titik dalam G terhubung (gambar a), sedangkan suatu graph G dikatakan tidak terhubung jika dan hanya jika ada 2 titik dalam G yang tidak terhubung (gambar b).
10. Komplemen
Misalkan G sebuah graph sederhana. Komplemen G dilambangkan dengan , adalah graph sederhana yang himpunan titiknya sama dengan himpunan titik G dan dua titik u dan v di berhubungan langsung jika dan hanya jika di G titik u dan v tidak berhubungan langsung.
11. Isomorfik
Dua graph G dan H dikatakan isomorfik ditulis , jika:
(i) Terdapat korespondensi satu-satu antara V(G) dan E(G),
(ii) Banyaknya sisi yang menghubungkan dua titik u dan v di G, sama dengan banyaknya sisi yang menghubungkan dua titik di H yang korespondensi dengan titik u dan titik v.
Graph G1 isomorfik dengan graph G2, sedangkan graph G1 tidak isomorfik dengan graph G3.

Referensi:
· Heri Sutamo, dkk. 2003. Matematika Diskrit. Bandung: Jurusan Matematika UPI & JICA.
· Ketut Budayasa. 1994. Matematika Diskrit. Surabaya: University Press Unesa.
· Ketut Budayasa. 2007. Teori Graph. Surabaya: University Press Unesa.
· Rinaldi Munir. ( ). Matematika Diskrit (edisi 3)., Informatika.
· A. Limbong, dkk. 2006. Matematika Diskrit. Bandung: CV. Utomo.
· Sumantri Slamet, dkk. 1991. Matematika Kombinatorik. Jakarta: Kelompok Gramedia.
· Jong Jek Siang. 2002. Matematika Diskrit dan Aplikasinya Pada Ilmu Komputer. Yokyakarta: Andi Yokyakarta.
· Purwanto. 1998. Teori Graph. Malang: Jurusan Pendidikan Matematika.
· C. L. Liu. 1995. Dasar-dasar Matematika Diskrit. Jakarta: PT. Gramedia.
· Richard Johnson Baugh. 1997. Matematika Diskrit (terjemahan). Yokyakarta: PT. Aditya Media.

GRAF

Posted on Maret 25, 2010 | Tinggalkan Komentar

Graf
1. Sejarah Graf
Graf dipakai pertama kali oleh seorang matematikawan Swis pada tahun 1763 untuk memecahkan teka-teki jembatan Konigsberg. Di kota Konigsberg –Jerman Timur– terdapat sungai Pregal yang dibelah dua oleh Pulau Kneipof. Daratan yang dipisahkan oleh sungai tersebut dihubungkan oleh tujuh buah jembatan. Teka-tekinya adalah : apakah mungkin melalui ketujuh jembatan tersebut dan kembali ke tempat semula dengan masing-masing jembatan dilalui tepa satu kali ?
Sebelum Euler memodelkan masalah ini ke dalam graf dan mengemukakan solusinya, kebanyakan orang sepakat bahwa tidak mungkin kembali ke tempat semula namun mereka tidak mampu menjelaskan mengapa. Euler memodelkan daratan dengan titik yang disebut sebagai simpul dan jembatan yang menghubungkannya sebagai garis yang disebut sebagai sisi.
Jawaban Euler adalah : orang tidak mungkin melalui ketujuh jembatan tersebut masing-masing satu kali dan kembali lagi ke tempat semula jika jumlah sisi dari masing-masing simpul tidak seluruhnya genap. Atau dengan kata lain, jika masing-masing simpul memiliki jumlah sisi genap maka dengan melalui masing-masing sisi satu kali kita dapat kembali ke tempat semula. Dari gambar di atas tampak bahwa simpul-simpul dari graf pemodelan jembatan Konigsberg memiliki sisi berjumlah ganjil, jadi orang tidak mungkin kembali ke tempat semula.
2 Definisi Graf
Graf adalah struktur diskrit yang terdiri dari simpul dan sisi dimana sisi-sisi menghubungkan simpul yang ada . Graf juga didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini :
V = himpunan tidak kosong dari simpul-simpul (vertex atau node) = {v₁,v₂,…v_n} dan
E = himpunan sisi-sisi (edges atau arcs) yang menguhubungkan sepasang simpul = {e₁,e₂,…e_n}
Atau dapat ditulis singkat notasi
G = (V,E) .
Simpul pada graf dinomori dengan huruf atau bilangan asli atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul vi dengan simpul vj dinyatakan dengan pasangan (vi,vj) atau dengan lambang e_i dimana i = himpunan bilangan asli = {1,2,3,…} .
Secara geometri graf direpresentasikan sebagai himpunan titik yang dihubungkan dengan himpunan garis dalam ruang dua dimensi.

3 Jenis-jenis Graf
Berdasarkan jenis sisinya graf digolongkan menjadi dua jenis :

1. Graf sederhana yaitu graf yang tidak memiliki sisi ganda maupun sisi loop.

2.   Graf tidak sederhana yaitu graf yang memiliki sisi ganda atau sisi loop. Graf tidak sederhana dibedakan menjadi dua :
a)     Graf ganda yaitu graf yang memiliki sisi ganda. Sisi ganda adalah sekumpulan sisi yang menghubungkan sepasang simpul yang sama. Dengan kata lain, bila sepasang simpul dihubungkan oleh lebih dari satu sisi, maka sisi-sisi itu disebut sisi ganda.
b) Graf semu yaitu graf yang memiliki sisi loop. Loop adalah sisi yang menghubungkan sebuah simpul dengan dirinya sendiri.
Berdasarkan jumlah simpul yang dimilikinya, graf juga digolongkan menjadi dua jenis:
1.      Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya berhingga.

1. Graf tak berhingga (unlimited graph)

Graf tak berhingga adalah graf yang jumlah simpulnya tak berhingga. Secara geometris graf tak berhingga digambarkan dengan sisi-sisi yang hanya memiliki satu simpul untuk setiap simpul luarnya. Sekilas nampak seperti graf yang belum selesai digambar.
Penggolongan lain dilakukan berdasarkan orientasi arah dari sisi-sisi graf. Ada dua jenis graf dalam penggolongan ini :
1. Graf tak berarah, yaitu graf yang sisi-sisinya tidak memiliki arah.
2. Graf Berarah, yaitu graf yang sisi-sisinya memiliki orientasi arah.
Pada graf jenis ini, sisi yang menghubungkan simpul 3 ke simpul 1 tidak sama dengan sisi yang menghubungkan simpul 1 ke simpul 3 karena orientasi arahnya berbeda.
4. Contoh Terapan Graf

1. Rangkaian listrik.

1. Isomer senyawa kimia karbon

metana (CH₄)                      etana (C₂H₆)              propana (C₃H₈)

1. graf dapat digunakan berbagai objek diskrit, terutama graf sering digunakan untuk memodelkan berbagai persoalan untuk memudahkan penyelesaiannya. Misalnya seseorang ingin menggambarkan diagram hubungan relasi kerja seorang pimpinan dengan staf-stafnya, maka sang pimpinan dapat dijadikan suatu objek diskrit (simpul/vertex), demikian juga staf-stafnya, dan akan terdapat sisi-sisi (edges) yang menghubungkan satu dan lainnya untuk menggambarkan hubungan (relationship) antara objek-objek (simpul) tadi.

Graf digunakan dalam kehidupan sehari-hari terutama untuk mendeskripsikan model persoalan dan menggambarkannya secara konkret dan jelas. Selain itu graf juga dipergunakan untuk mempermudah menyelesaikan berbagai macam persoalan-persoalan yang sulit diselesaikan dengan perhitungan dan pertimbangan biasa. Hal ini disebabkan sifat-sifat dan teori-teori yang telah dipelajari pada graf.