Chulalongkorn University Theses and Dissertations (Chula ETD)
Path algebras for solving some path problems
Other Title (Parallel Title in Other Language of ETD)
พีชคณิตวิถีเพื่อการหาผลเฉลยของปัญหาวิถีบางปัญหา
Year (A.D.)
1992
Document Type
Thesis
First Advisor
Wanida Hemakul
Faculty/College
Graduate School (บัณฑิตวิทยาลัย)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Mathematics
DOI
10.58837/CHULA.THE.1992.835
Abstract
A path algebra is a semiring (P, [+], [x]) with unit and zero such that the operation [+] is idempotent and commutative. This thesis is concerned with the algebraic aspect (which is described by path algebras) of the following path problems on hypergraphs (1) enumeration of all independent node sets, (2) enumeration of all matchings (independent edge sets). (3) enumeration of all simple paths between two given nodes. (4) enumeration of all elementary paths between two given nodes. Then the solution of such problems can be obtained by solving an algebraic equation with the use of computers.
Other Abstract (Other language abstract of ETD)
พีชคณิตวิถีคือเซมิริง (P, [+], [x]) ที่มีเอกลักษณ์และศูนย์ ซึ่งการดำเนินการ [+] มีคุณสมบัติ ไอเดมโพเทนต์และสลับที่ วิทยานิพธ์นี้เกี่ยวข้องในแง่พีชคณิต (ซึ่งอธิบายได้ด้วยพีชคณิตวิถี) ของปัญหาวิถีบนไฮเพอร์กราฟ ดังต่อไปนี้ 1. การแจงนับเซตของจุดยอดทั้งหมดที่เป็นอิสระ 2. การแจงนับเซตของการจับคู่ทั้งหมด (เซตของด้านทั้งหมดที่เป็นอิสระ) 3. การแจงนับวิถีเชิงเดียวทั้งหมดระหว่างโนดสองโนดที่กำหนดให้ 4. การแจงวิถีเชิงธาตุมูลทั้งหมดระหว่างโนดที่กำหนดให้เราสามารถหาผลเฉลยของปัญหาเหล่านี้ด้วยสมการพีชคณิตและใช้คอมพิวเตอร์เข้าช่วย
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Anansuvanchai, Somsak, "Path algebras for solving some path problems" (1992). Chulalongkorn University Theses and Dissertations (Chula ETD). 38399.
https://digital.car.chula.ac.th/chulaetd/38399