ĐA THỨC TUTTE CỦA MỘT SỐ ĐỒ THỊ

Tập 18 > Chuyên san Toán - Công nghệ thông tin - Vật lý - Kiến trúc

Ngày nhận bài: 14/9/2020; ngày hoàn thành phản biện: 21/9/2020; ngày duyệt đăng: 22/10/2020

ĐA THỨC TUTTE CỦA MỘT SỐ ĐỒ THỊ

Lê Mạnh Hà, Hoàng Ngọc Phú

Email: lemanhhavn@gmail.com

Tóm tắt

Trong bài báo này, chúng tôi sẽ tính toán đa thức Tutte của một số đồ thị đơn giản. Sử dụng đa thức Tutte để tính số cây bao trùm của một đồ thị. Qua đó, chúng tôi sẽ chỉ ra mối liên hệ giữa số cây bao trùm và định thức của ma trận Laplace thu gọn của đồ thị.

Từ khóa: cây bao trùm, đồ thị vòng, đa thức Tutte, định lý ma trận cây, ma trận Laplace


THE TUTTE POLYNOMIAL OF SOME GRAPHS

Le Manh Ha, Hoang Ngoc Phu

Email: lemanhhavn@gmail.com

Abstract

In this paper, we compute the Tutte polynomial of some graphs. We use the Tutte polynomial to calculate the number of spanning trees of the graph. Thereby, we can confirm that the number of spanning trees is equal to the determinant of Laplace matrix of a graph.

Keywords: Cycle graph, Laplace matrix, Matrix-tree Theorem, Spanning tree, Tutte polynomial

File đính kèm

Tạp chí
Khoa học và Công nghệ

Trường Đại học Khoa học, Đại học Huế

tapchidhkh@hueuni.edu.vn

0234.3837847

77 Nguyễn Huệ, TP Huế