EULLER dan PEWARNAAN GRAF

1.      Teori EULER

Suatu multigraph berhingga dan terhubung adalah eulerian jika dan hanya jika derajat setiap vertexnya genap.
Multigraph bisa dikatakan euler jika suatu graph yang hanya memiliki trail
Formula EULER
V – E + R = 2
Ket :
V = Vertex
E = Edge
R = Region

2.      Pewarnaan graf adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu.
Ada tiga macam pewarnaan graf.

Pertama, pewarnaan titik (vertex coloring) yaitu memeberikan warna berbeda pada setiap titik yang bertetangga sehingga tidak ada dua titik yang bertengga dengan warna yang sama.

Kedua, pewarnna sisi (edge coloring), yaitu memberikan warna berbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga memepunya warna yang sama.

Ketiga, pewarnaan bidang, yaitu memberikan warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama.

Adapun aplikasi dari pewarnan graf adalah masalah penjadwalan, daftra alokasi, permainan sudoku, dll.