GRAF

Graf adalah sebuah relasi atau himpunan dari V dan himpunan E.

Perjalanan Euller adalah perjalanan dari suatu simpul kembali ke simpul tersebut dengan melewati jembatan setiap ruas tepat satu kali.

Perjalanan Euller akan terjadi jika :

*Graf terhubung

*Banyak nya ruas yang datang pada setiap simpul jumlah nya genap.

Keterhubungan Graf :

*Perjalanan (walk) adalah suatu urutan dari simpul, ruas, simpul, ruas yang saling menyambung atau barisan simpul dengan ruas berganti - ganti.

*Trail (Lintasan) adalah suatu walk dengan syarat tidak memiliki ruas yang sama/ ruas nya berbeda.

*Path (jalur) adalah walk dengan setiap simpulnya berbeda.

*Sirkuit adalah trail tertutup dengan semua simpul berderajat dua.

Beberapa jenis Graf :

*Graf lengkap yaitu Graf sederhana dimana setiap dua simpul selalu bertetangga.

*Graf reguler yaitu graf dimana derajat setiap simpul nya sama.

*Graf hampa(nol) yaitu graf tanpa ruas atau graf dengan setiap simpul terpencil.

*Graf bipartisi yaitu graf yang setiap simpul - simpul nya dapat dikelompokkan kedalam dua himpunan yang saling lepas, dimana tidak ada simpul - simpul yang berpasangan terletak dalam suatu himpunan.

*Graf bipartisi lengkap yaitu setiap simpulnya di satu ruas memiliki pasangan di ruas yang lainnya atau setiap elemen himpunan memiliki tetangga di himpunan lawannya.

Istilah - istilah dalam Graf :

*Order : banyak nya vertex

*size : banyak nya ruas

*Ruas sejajar : ruas yang menghubungkan dua simpul yang sama

*self loop : ruas yang kedua ujung simpul nya sama.

*Multigraf: sebuah graf yang mempunya self loop.

*Isomorfisma : dua graf atau lebih yang mempunyai jumla ruas, jumlah simpul, dan derajat simpul yang sama.

*Homomorfisma : dua graf atau lebih yang penggambarannya sama tetapi banyak nya ruas dan simpul berbeda.