Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Hypermap grammar for planar K-Tree maps
Year (A.D.)
2022
Document Type
Thesis
First Advisor
อรรถสิทธิ์ สุรฤกษ์
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
วิศวกรรมศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิศวกรรมคอมพิวเตอร์
DOI
10.58837/CHULA.THE.2022.866
Abstract
วิศวกรและนักวิทยาศาสตร์ต่างเผชิญกับปัญหาที่มีโครงสร้างซับซ้อนมากยิ่งขึ้น และต้องการเครื่องมือทางคณิตศาสตร์ที่เหมาะสมเพื่ออธิบายปัญหาเหล่านี้ แม้กราฟจะเป็นเครื่องมือที่นิยมใช้แสดงระบบที่ซับซ้อน แต่ก็ยังขาดส่วนประกอบบางอย่างที่สำคัญต่อการรับรู้ความซับซ้อนของวัตถุทางเรขาคณิต ซึ่งสามารถแสดงแทนได้ด้วยแมพและไฮเพอร์แมพ เนื่องจากมีองค์ประกอบหลักที่เรียกว่า หน้า เพิ่มเติมจากส่วนประกอบพื้นฐานอื่น ๆ ในกราฟ จึงเป็นเครื่องมือที่ครอบคลุมและยืดหยุ่นยิ่งขึ้นในการแสดงและวิเคราะห์โครงสร้างเชิงเรขาคณิต งานวิจัยนี้จะเสนอแนวทางใหม่ในการผลิตแมพโดยใช้ไวยากรณ์ไฮเพอร์แมพ โดยปรับการดำเนินการต่าง ๆ ที่เกี่ยวข้องกับไฮเพอร์แมพให้นิยามบนจุดยอดและหน้า แทนวิธีการเดิมซึ่งนิยามบนจุดยอดและเส้นเชื่อม เพื่อให้มีความยืดหยุ่นในการควบคุมและจัดการเกี่ยวกับหน้าของไฮเพอร์แมพ เนื่องจากหน้ามีบทบาทสำคัญในการนิยามไฮเพอร์แมพ โดยเฉพาะอย่างยิ่งในกรณีของแมพเชิงระนาบ ไวยากรณ์ที่นำเสนอในงานนี้แสดงให้เห็นถึงความสามารถในการทำความเข้าใจและตรวจจับโครงสร้างย่อยของไฮเพอร์แมพ โดยยกตัวอย่างการสร้างแมพเชิงระนาบของกราฟเชิงต้นไม้อันดับเค (เมื่อเคเป็นจำนวนเต็มบวกที่มีค่าไม่เกินสาม) โดยใช้ไวยากรณ์ไฮเพอร์แมพที่มีเพียงกฎการผลิตเดียว ผลการวิจัยแสดงให้เห็นถึงศักยภาพในการนำไวยากรณ์ที่นำเสนอในงานนี้ไปใช้เป็นเครื่องมือในการศึกษาคุณสมบติและโครงสร้างของแมพเชิงระนาบ รวมถึงการนำไปประยุกต์ใช้ในสายงานต่าง ๆ เช่น วิทยาการคอมพิวเตอร์ ทอพอโลยี และทฤษฎีกราฟ
Other Abstract (Other language abstract of ETD)
Engineers and scientists are constantly dealing with increasingly complex models that require suitable mathematical frameworks to describe them. While graphs are commonly used to represent complex systems, maps and hypermaps are more general structures useful for representing and analyzing geometric objects, thanks to additional basic elements that graphs lack, such as faces. In this research, a novel method for constructing maps using hypermap grammar is proposed. Unlike traditional approaches that rely on vertices and edges to define submaps, this method utilizes vertices and faces to identify and manipulate structures with greater flexibility, since faces play a crucial role in defining maps, especially when they are planar. Our grammar is shown to be effective in both understanding and detecting the structure of the generated maps. By employing a single production rule, the new hypermap grammar generates planar k-tree maps (where k = 1, 2, or 3). The findings suggest that the new hypermap grammar presented in this research has the potential to be a valuable tool for examining the properties and structure of planar maps, with potential applications in diverse fields such as computer science, topology, and graph theory.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
โคเมฆารัตน์, วรวุฒิ, "ไวยากรณ์ไฮเพอร์แมพสำหรับแมพเชิงต้นไม้อันดับเคเชิงระนาบ" (2022). Chulalongkorn University Theses and Dissertations (Chula ETD). 6576.
https://digital.car.chula.ac.th/chulaetd/6576