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. การแจงวิถีเชิงธาตุมูลทั้งหมดระหว่างโนดที่กำหนดให้เราสามารถหาผลเฉลยของปัญหาเหล่านี้ด้วยสมการพีชคณิตและใช้คอมพิวเตอร์เข้าช่วย

Share

COinS