TAILIEUCHUNG - Báo cáo toán học: "Interchangeability of Relevant Cycles in Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Interchangeability of Relevant Cycles in Graphs. | Interchangeability of Relevant Cycles in Graphs Petra M. Gleiss Josef LEyDGLD6 AND Peter F. Stadler Institute for Theoretical Chemistry and Molecular Structural Biology University of Vienna Wahringerstrasse 17 A-1090 Vienna Austria Phone 43 1 4277-52737 Fax 43 1 4277-52793 E-Mail pmg studla @ URL http pmg studla 6Dept. for Applied Statistics and Data Processing University of Economics and Business Administration Augasse 2-6 A-1090 Wien Austria Phone 43 1 31336-4695 Fax 43 1 31336-738 E-Mail .at URL http staff leydold Address for correspondence cThe Santa Fe Institute 1399 Hyde Park Road Santa Fe NM 87501 USA Phone 505 984 8800 Fax 505 982 0565 E-Mail stadler@ URL http studla Submitted July 26 1999 Accepted March 12 2000. Abstract The set R of relevant cycles of a graph G is the union of its minimum cycle bases. We introduce a partition of R such that each cycle in a class W can be expressed as a sum of other cycles in W and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class W. This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally we give a polynomial-time algorithm to compute this partition. Keywords Minimum Cycle Basis Relevant Cycles AMS Subject Classification Primary 05C38. Secondary 05C85 92D20 92E10. THE ELECTRONIC JOURNAL OF COMBINATORICS 7 2000 R16 2 1. Introduction Cycle bases of graphs have a variety of applications in science and engineering. For example applications occur in structural flexibility analysis 9 electrical networks 3 and in chemical structure storage and retrieval systems 5 . Brief surveys and extensive references can be found in 8 7 . The set R of relevant cycles of a graph G is the union of its minimum cycle bases 12 15 . We define an equivalence relation interchangeability on R such that the .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.