کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9513190 | 1632459 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Activity preserving bijections between spanning trees and orientations in graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 298, Issues 1â3, 6 August 2005, Pages 169-188
Journal: Discrete Mathematics - Volume 298, Issues 1â3, 6 August 2005, Pages 169-188
نویسندگان
Emeric Gioan, Michel Las Vergnas,