Theory Graph

"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

Diameter dari  graph adalah  distance terpendek yang dapat ditemukan antara dua vertex.

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?