2.2.4 Bersisian (Incidency)

Untuk sembarang ruas e = (vj, vk) dikatakan :
e bersisian dengan simpul vj , atau
e bersisian dengan simpul vk

2.2.3 Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung

2.2.2 Derajat (Degree)

2.2.1 Subgraf dan Komplemen Subgraf

2.1.2.4 Graf Berhingga

Graf berhingga (limited graf)
Graf berhingga adalah graf yang jumlah simpulnya n, berhingga.

2.1.2.3 Graf tak-berarah

Graf tak-berarah (undirected graf)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.

2.1.2.2 Graf tak-sederhana

Graf tak-sederhana (unsimple graf/multigraf)

Graf yang mengandung ruas ganda atau gelung (loop) dinamakan graf tak-sederhana (unsimple graf atau multigrapf).

2.1.2.1 Graf Sederhana

Graf Sederhana (simple graf).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.

2.1.2 Jenis-jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis :
Graf sederhana (simple graf)
Graf tak-sederhana (unsimple graf/multigraf)

Berdasarkan orientasi arah pada sisi, yaitu :
Graf tak-berarah (undirected graf)

Berdasarkan jumlah simpul pada suatu graf,yaitu :
Graf berhingga (limited graf)

2.1.1 Definisi Graf

Graf G (V, E), adalah koleksi atau pasangan dua himpunan

1. Himpunan V yang elemennya disebut simpul atau titik, atau vertex, atau point, atau node.
2. Himpunan E yang merupakan pasangan tak terurut dari simpul, disebut ruas atau rusuk, atau sisi, atau edge, atau line.

2.1 Konsep Dasar Graf

1.1 Latar Belakang Permasalahan

Teori graf merupakan salah satu bidang matematika, yang diperkenalkan pertama kali oleh ahli matematika asal Swiss, Leonardo Euler pada tahun 1736. Ide besarnya muncul sebagai upaya menyelesaikan masalah jembatan Konisberg. Dari permasalahan itu, akhirnya Euler mengembangkan beberapa konsep mengenai Teori graf.
Dalam teori graf, konsep graf bipartit dapat digunakan untuk memodelkan hubungan antara dosen dan kelas yang diajarnya. Kemudian konsep matching dapat digunakan untuk mengelompokkan pasangan dosen-kelas yang dapat menyelenggarakan kegiatan belajar mengajar dalam waktu yang sama. Kelompok – kelompok dosen-kelas tersebut kemudian ditempatkan kedalam slot waktu dengan urutan yang memenuhi syarat yang berlaku.

1.2 Perumusan Masalah

Graf G (V,E) yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G(V1, V2). Sedangkan pewarnaan sisi adalah cara pemberian warna pada garis sedemikian rupa sehingga setiap garis yang terkait pada titik yang sama diberi warna yang berbeda. Kemudian graf G didekomposisi menjadi kelompok subgraf dimana setiap subgraf hanya memuat sisi di G dengan warna yang sama. Masing – masing subgraf tersebut adalah matching di graf bipartit G. Proses tersebut dinamakan dekomposisi graf bipartit menjadi matching.

1.3 Batasan Masalah

Pada skripsi ini graf yang dikaji adalah graf sederhana, graf tak-sederhana graf hingga, dan graf tak-berarah. Dimana graf sederhana adalah graf yang tidak memuat loop dan sisi rangkap (multiple edges). Loop adalah sisi yang menghubungkan suatu titik dengan dirinya sendiri. Jika terdapat lebih dari satu sisi yang menghubungkan dua titik, maka sisi-sisi tersebut dinamakan sisi rangkap. Graf tak-sederhana adalah graf yang memuat loop dan sisi rangkap (multiple edges), dibatasi graf tak-sederhana yang tidak memuat loop. Sedangkan graf hingga didefinisikan sebagai graf yang mempunyai order terbatas. Order didefinisikan sebagai banyaknya titik yang ada dalam graf. Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.

1.4 Sistematika Pembahasan

Sistematika penulisan dalam penelitian ini adalah sebagai berikut :
BAB I Pendahuluan
Bab ini menjelaskan latar belakang permasalahan, perumusan masalah, batasan masalah, dan sistematika pembahasan.
BAB II Landasan teori
Bab ini menguraikan teori yang menjadi dasar dan penunjang dalam dekomposisi graf bipartit menjadi matching.
BAB III Kajian Matematis dalam dekomposisi graf bipartit menjadi matching.
BAB IV Studi kasus
Bab ini menjelaskan tentang studi kasus yang berkaitan dengan perumusan masalah dengan menggunakan kajian matematis dalam Teori graf.
BAB V Kesimpulan dan saran
Bab ini berisikan tentang kesimpulan dan saran yang telah diperoleh berdasarkan analisa dari BAB IV, sesuai dengan apa yang diharapkan pada tujuan dan manfaat dari dekomposisi graf bipartit menjadi matching ini.

A Scheduling Problem