Kusumaningrum, Atika Norma Larasati, 4150407003 (2012) Teorema Menger pada Graf. Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF (Teorema Menger pada Graf.) - Published Version Download (78kB) | Preview

Abstract

Teori graf merupakan pokok bahasan matematika yang digunakan untuk merepresentasikan objek-objek diskrit dan hubungannya antara objek-objek tersebut. Graf didefinisikan sebagai pasangan himpunan , yang dalam hal ini adalah himpunan tidak kosong dari titik-titik (vertices) dan adalah himpunan sisi (edges) yang menghubungkan satu atau dua titik. Salah satu konsep penting dalam graf adalah teorema Menger, karena dengan teorema Menger dapat dengan mudah dicari banyak lintasan disjoin maksimum di antara dua titik tanpa harus menyelidiki bermacam-macam lintasan pada graf. Permasalahan dalam skripsi ini adalah apa yang dimaksud dengan teorema Menger dan bagaimana sifat dan penggunaan teorema Menger pada graf. Metode penelitian yang digunakan adalah metode studi pustaka, yaitu melakukan kajian pustaka dari berbagai sumber yang berkaitan dengan permasalahan sehingga didapat suatu ide mengenai bahan dasar pengembangan upaya pemecahan masalah. Dalam skripsi ini dibahas tentang teorema Menger berserta pembuktiannya dan penggunaan teorema Menger pada graf. Pada teorema Menger versi titik, misalkan dan sebarang titik dari graf dengan . Maka nilai minimum dari -cut sama dengan nilai maksimum dari banyaknya lintasan disjoin titik dari ke . Sedangkan pada teorema Menger versi sisi, misalkan dan sebarang titik dari graf . Maka nilai minimum dari -disconnecting set sama dengan nilai maksimum dari banyaknya lintasan disjoin sisi dari ke . Kemudian teorema Menger dapat pula digunakan untuk membuktikan teorema Hall pada Matching. Skripsi ini baru dikaji teorema Menger pada graf tidak berarah. Disarankan penelitian tentang teorema Menger pada graf ini dapat dikembangkan lagi untuk graf berarah.

Actions (login required)

View Item