ไวยากรณ์ไฮเพอร์แมพสำหรับแมพเชิงต้นไม้อันดับเคเชิงระนาบ

Hypermap grammar for planar K-Tree maps

Name: วรวุฒิ โคเมฆารัตน์

Abstract: วิศวกรและนักวิทยาศาสตร์ต่างเผชิญกับปัญหาที่มีโครงสร้างซับซ้อนมากยิ่งขึ้น และต้องการเครื่องมือทางคณิตศาสตร์ที่เหมาะสมเพื่ออธิบายปัญหาเหล่านี้ แม้กราฟจะเป็นเครื่องมือที่นิยมใช้แสดงระบบที่ซับซ้อน แต่ก็ยังขาดส่วนประกอบบางอย่างที่สำคัญต่อการรับรู้ความซับซ้อนของวัตถุทางเรขาคณิต ซึ่งสามารถแสดงแทนได้ด้วยแมพและไฮเพอร์แมพ เนื่องจากมีองค์ประกอบหลักที่เรียกว่า หน้า เพิ่มเติมจากส่วนประกอบพื้นฐานอื่น ๆ ในกราฟ จึงเป็นเครื่องมือที่ครอบคลุมและยืดหยุ่นยิ่งขึ้นในการแสดงและวิเคราะห์โครงสร้างเชิงเรขาคณิต งานวิจัยนี้จะเสนอแนวทางใหม่ในการผลิตแมพโดยใช้ไวยากรณ์ไฮเพอร์แมพ โดยปรับการดำเนินการต่าง ๆ ที่เกี่ยวข้องกับไฮเพอร์แมพให้นิยามบนจุดยอดและหน้า แทนวิธีการเดิมซึ่งนิยามบนจุดยอดและเส้นเชื่อม เพื่อให้มีความยืดหยุ่นในการควบคุมและจัดการเกี่ยวกับหน้าของไฮเพอร์แมพ เนื่องจากหน้ามีบทบาทสำคัญในการนิยามไฮเพอร์แมพ โดยเฉพาะอย่างยิ่งในกรณีของแมพเชิงระนาบ ไวยากรณ์ที่นำเสนอในงานนี้แสดงให้เห็นถึงความสามารถในการทำความเข้าใจและตรวจจับโครงสร้างย่อยของไฮเพอร์แมพ โดยยกตัวอย่างการสร้างแมพเชิงระนาบของกราฟเชิงต้นไม้อันดับเค (เมื่อเคเป็นจำนวนเต็มบวกที่มีค่าไม่เกินสาม) โดยใช้ไวยากรณ์ไฮเพอร์แมพที่มีเพียงกฎการผลิตเดียว ผลการวิจัยแสดงให้เห็นถึงศักยภาพในการนำไวยากรณ์ที่นำเสนอในงานนี้ไปใช้เป็นเครื่องมือในการศึกษาคุณสมบติและโครงสร้างของแมพเชิงระนาบ รวมถึงการนำไปประยุกต์ใช้ในสายงานต่าง ๆ เช่น วิทยาการคอมพิวเตอร์ ทอพอโลยี และทฤษฎีกราฟ

Abstract: 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.

จุฬาลงกรณ์มหาวิทยาลัย. สำนักงานวิทยทรัพยากร

Address: กรุงเทพมหานคร

Email: cuir@car.chula.ac.th

Name: อรรถสิทธิ์ สุรฤกษ์

Role: ที่ปรึกษา

Created: 2565

Modified: 2567-10-13

Issued: 2567-10-13

วิทยานิพนธ์/Thesis

application/pdf

URL: http://doi.org/10.58837/CHULA.THE.2022.866

tha

DegreeName: วิศวกรรมศาสตรมหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมคอมพิวเตอร์

Grantor: จุฬาลงกรณ์มหาวิทยาลัย

©copyrights จุฬาลงกรณ์มหาวิทยาลัย

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	5970454021.pdf	1.9 MB

ใช้เวลา

0.027496 วินาที