สภาพเชื่อมโยงอวัฏจักรของกราฟเชื่อมโยง

Abstract

จากทฤษฎีกราฟในเรื่องเซตตัดจุด (vertex cut) ของกราฟเชื่อมโยงไม่ชัด G มีการศึกษาถึงเซตตัดจุดที่มีขนาดเล็กที่สุด U ซึ่งทำให้กราฟ G-U เป็นกราฟไม่เชื่อมโยง โดยไม่สนใจส่วนประกอบที่เกิดขึ้นของกราฟ G-U จึงทำให้เกิดแนวคิดที่จะศึกษาเซตตัดจุด U ที่มีขนาดเล็กที่สุดที่ทำให้ส่วนประกอบของ G-U เป็นกราฟป่าไม้ เพื่อให้เกิดองค์ความรู้ใหม่ในเรื่องเซตตัดจุดและเพื่อให้ศึกษาทฤษฎีกราฟมีแนวคิดกว้างขวางขึ้น อันจะก่อให้เกิดความเข้าใจและนำไปประยุกต์ใช้ต่อไป ในงานวิจัยนี้ ได้ศึกษาเฉพาะเซตตัดจุด U ที่ทำให้ผลจากการดึงจุดเหล่านั้นออกไปแล้ว ทำให้กราฟ G-U เป็นกราฟไม่เชื่อมโยงที่ไม่มีวัฏจักร หรือเป็นกราฟชัด เราเรียกเซต U ว่าเซตอวัฏจักร (acyclic set) และเรียกขนาดของเซตอวัฏจักรที่มีขนาดเล็กที่สุดนี้ว่า สภาพเชื่อมโยงอวัฏจักร (acyclic connectivity) โดยใช้สัญลักษณ์ K(G) จากการทำงานวิจัยนี้ เราสามารถหาสภาพเชื่อมโยงอวัฏจักรของกราฟบริบูรณ์ และกราฟ k-ส่วนบริบูรณ์ และได้แสดงกราฟทั้งหมดที่มีอันดับ n>=3 ที่มีสภาพเชื่อมโยงอวัฏจักร 1, 2, n-1 และ n-2 นอกจากนี้ ได้พบว่า สำหรับทุกค่า k และ n ซึ่ง 1<=k<=n-1 จะมีกราฟเชื่อมโยงที่มีอันดับ n และสภาพเชื่อมโยงอวัฏจักร k