Abstract
Kajian literatur tentang teori graf, khususnya planaritas suatu graf, yaitu menentukan apakah suatu graf itu termasuk graf planar atau bukan sudah banyak dibahas. Pada artikel ini pembahasan sedikit berbeda yaitu melakukan generalisasi atau perumuman teorema planaritas untuk dan teorema planaritas untuk Eksistensi perumuman ini penting karena dapat membuktikan planaritas dan sekaligus serta planaritas beberapa graf yang terkait. Pembuktian ketidakplanaran graf lengkap dan memberikan manfaat besar terhadap pengembangan teori planaritas graf dan memantapkan jaminan kebenaran pada terapannya. Urgensi pembuktiannya memiliki peran yang besar dalam menentukan planaritas graf-graf yang terkait, baik isomorfik atau subdivisi. Salah satu produk yang dihasilkan adalah teorema Kuratovski yang memberikan syarat perlu dan cukup suatu graf merupakan graf planar. Proses generalisasi dilakukan melalui kajian terhadap sifat-sifat khusus pada dan juga sifat-sifat khusus yang dimiliki . Sifat-sifat khusus tersebut diperumum sehingga diperoleh suatu sifat yang berlaku baik untuk maupun . Berdasarkan hasil generalisasi dari sifat tersebut, kemudian dikombinasikan dengan teorema pertidaksamaan Euler menghasilkan suatu teorema yaitu jika suatu graf planar terhubung, dan panjang sikel terpendeknya adalah , dengan maka berlaku £ Manfaat dari generalisasi ini dapat juga digunakan pada pembuktian dan secara langsung dan beberapa graf terkait secara mudah. Generalization of Euler's Inequality to Prove Planarity of Graphs K_5 and K_(3,3)
Abstract
The study of literature on graph theory, especially the planarity of a graph, which is to determine whether a graph is a planar graph or a non-planar graph, has been widely discussed. This article's discussion is slightly different, namely generalizing the planarity theorem for and the planarity theorem for This generalization is important because it can prove the planarity of and and the planarity of several related graphs. Proving the unplanarity of complete graphs and provide significant benefits to developing graph planarity theory and strengthens the guarantee of truth in its application. The urgency of the proof has a significant role in determining the planarity of the related graphs, either isomorphic or subdivision. One of the products of its role is the birth of Kuratovski's theorem, which provides the necessary and sufficient conditions for a planar graph. The generalization process is carried out by studying the special properties of and . These unique properties are generalized to obtain a valid property for and . Based on the results of the generalization of these properties, then combined with the Euler inequality theorem and the resulting theorem is if is a planar graph, connected, and the length of the shortest cycle is k, with then applies £ (n-2). The benefits of this generalization can be used to prove and directly and some related graphs quickly.
Penulisan artikel ini bertujuan untuk melakukan generalisasi atau perumuman teorema planaritas untuk K_5 dan teorema planaritas untuk K_3,3. Eksistensi perumuman teorema ini penting karena dapat membuktikan planaritas K_5 dan sekaligus K_3,3 serta planaritas beberapa graf yang terkait. Article ini merupakan hasil kajian literatur tentang teori graf, khususnya planaritas suatu graf, yaitu menentukan apakah suatu graf itu termasuk graf planar atau graf tidak planar. Pembuktian ketidakplanaran graf lengkap K_5 dan K_3,3 memberikan manfaat besar terhadap pengembangan teori planaritas graf dan memantapkan jaminan kebenaran pada terapannya. Urgensi pembuktiannya memiliki peran yang besar dalam menentukan planaritas graf-graf yang terkait, baik isomorfik atau subdivisi. Salahsatu produk perannya adalah lahirnya teorema Kuratovski yang memberikan syarat perlu dan cukup suatu graf planar. Teorema Kurotavski menjelaskan bahwa suatu graf G adalah planar jika dan hanya jika G tidak memuat subgraph yang isomorfik dengan K5 atau K3,3 atau sebarang graf subdivisi dari K5 atau K3,3. Proses generalisasi teorema dilakukan melalui kajian terhadap sifat-sifat khusus pada K_5 dan sifat-sifat khusus yang dimiliki K_3,3. Sifat-sifat khusus tersebut diperumum sehingga diperoleh suatu sifat yang berlaku baik untuk K_5 dan K_3,3. Berdasarkan hasil generalisasi sifat tersebut, kemudian dikombinasikan pada teorema pertidaksamaan Euler dan dihasilkan teorema yaitu jika G suatu graf planar, terhubung, |V(G)|=n, |E(G)|=m dan panjang sikel terpendeknya adalah k, dengan k3 maka berlaku . Teorema generalisasi ini mampu membuktikan K_5 dan K_3,3 secara langsung dan beberapa graf terkait secara mudah.
Recommended Citation
Emut, E. (2022). Generalisasi Pertidaksamaan Euler untuk Membuktikan Planaritas Graf K_5 dan K_(3,3). PYTHAGORAS : Jurnal Matematika dan Pendidikan Matematika, 17(2), 475-488. https://doi.org/10.21831/pythagoras.v17i2.51400
