"Theory Graph"
Oleh : Heru Susanto, S.Kom
Pada cabang matematika yang disebut Teori Graf, suatu Graf tidak berhubungan dengan graf yang menggambarkan data, seperti kemajuan bursa saham atyau pertumbuhan planet.
Di dalam teori Graf, graf adalah kumpulan titik yang mungkin terhubung maupun tidak terhubung dengan titik lainnya dengan garis. Tidak penting seberapa besar titik itu, atau seberapa panjang garisnya, atau apakah garis itu lurus atau melengkung. Dan titik itupuntidak harus bulat.
Intinya adalah bahwa titik – titik itu terhubung oleh garis.
Dua titik dapat hanya terhubung dengan satu garis. Jika dua titik terhubung dengan satu garis, maka tidak "legal" menggambarkan garis lain untuk menghubungkan kedua titik tersebut, bahkan jika garis itu merentang jauh dari titik pertama.
Ada beberapa terminologi dari teori graf yang digunakan untuk menjelaskan apa yang dilihat ketika melihat suatu graf.
Edge dan vertex dari graf
Sebuah graf dibentuk dari kumpulan titik yang dihubungkan dengan garis - garis.
Titik – titik tersebut disebut vertex.
Garis – garisnya disebut edge.Degree dari vertex pada sebuah graph
Degree dari vertex pada sebuah graf adalah jumlah edges yang berada pada vertex tersebut.
Angka pada setiap vertex dari graf ini adalah degree dari vertex tersebut
- edge
- vertex
- degree
- size
- regular
- path
- circuit
- cycle
- hamiltonain
- eulerian
- planar
- non-planar
- distance
- diameter
- isomorphic
- complete
Size dari Graf
Size dari graf adalah jumlah vertex yang dimilikinya.
Graf Regular
Suatu graf dikatakan regular jika setiap vertex mempunyai degree yang sama.
Path dan Cycle dalam graf
Path adalah lintasan yang melalui edge dan vertex dalam graf. Semua vertex dan edge dalam lintasan dihubungkan satu dengan yang lain.
Cycle adalah lintasan yang dimulai dan berakhir pada vertex yang sama. Cycle kadang – kadang disebut circuit.
Jumlah edge dalam lintasan atau cycle disebut length (panjang) lintasan. Apakah panjang lintasan juga merupakan julah vertex?
Lintasan Hamilton
Lintasan hamilton adalah lintasan yang melalui setiap vertex dalam graf tepat satu kali, tetapi lintasan hamiltonain tidak perlu melalui semua edge.
Lintasan hamilton yang berawal dan berakhir di tempat yang sama disebut circuit hamilton.Lintasan Euler
Lintasan euler adalah lintasan yang melalui setiap edge dalam graf tepat satu kali. Lintasan euler mungkin melalui sebuah vertex lebih dari satu kali.
Lintasan euler yang berawal dan berakhir di tempat yang sama disebut circuit euler.
Graf Planar
Adalah graph yang dapat digambarkan sedemikian tidak ada edge yang saling berpotongan.
Distance
Distance antara dua vertex adalah angka yang menunjukkan jumlah edge yang dilalui ketika kita melakukan perjalanan dari satu vertex ke vertex lain.
Jika terdapat lebih dari satu lintasan atara dua vertex , maka jumlha edge dengan lintasan terpendek itulah yang disebut distance.
Jumlah edge dalam lintasan disebut length (panjang) dari lintasan.
The Diameter of a Graph
Ketika kita mngukur distance untuk menentukan diameter graf, ingat kembali bahwa jika dua vertiex mempunyai banyak lintasan , maka kita hanya menghitung yang terpendek.Complete Graph (Graf Lengkap)
Dalam complete graph, setiap pasang vertex dihubungkan oleh satu edge. Tidak mungkin menambahkan edge lagi ke dalam graf lengkap karena setiap edge yang mungkin telah digambarkan.
Complete graphs selalu mempunyai diameter 1. Mengapa?
Baca Selengkapnya >>>
. Salah satu situs yang memberikan layanan ini adalah 
