کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872368 681740 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposition theorem on matchable distributive lattices
ترجمه فارسی عنوان
نظریه تقسیم بر روی شبکه های قابل توزیع توزیعی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A distributive lattice structure M(G) has been established on the set of perfect matchings of a plane bipartite graph G. We call a lattice matchable distributive lattice (simply MDL) if it is isomorphic to such a distributive lattice. It is natural to ask which lattices are MDLs. We show that if a plane bipartite graph G is elementary, then M(G) is irreducible. Based on this result, a decomposition theorem on MDLs is obtained: a finite distributive lattice L is an MDL if and only if each factor in any cartesian product decomposition of L is an MDL. Two types of MDLs are presented: J(m×n) and J(T), where m×n denotes the cartesian product between m-element chain and n-element chain, and T is a poset implied by any orientation of a tree.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 166, 31 March 2014, Pages 239-248
نویسندگان
, , ,