TAILIEUCHUNG - Báo cáo toán học: "On the Theory Of Pfaffian Orientations. II. T -joins, k-Cuts, and Duality of Enumeration"

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: On the Theory Of Pfaffian Orientations. II. T -joins, k-Cuts, and Duality of Enumeration. | On the Theory Of Pfaffian Orientations. II. T-joins k-Cuts and Duality of Enumeration. Anna Galluccio Istituto di Analisi dei Sistemi ed Informatica - CNR viale Manzoni 30 00185 Roma ITALY galluccio@ yMartin Loebl Department of Applied Mathematics Charles University Malostranske n. 25 118 00 Praha 1 CZECH REPUBLIC loebl@ Received February 18 1998 Accepted May 22 1998. Abstract This is a continuation of our paper A Theory of Pfaffian Orientations I Perfect Matchings and Permanents . We present a new combinatorial way to compute the generating functions of T-joins and k-cuts of graphs. As a consequence we show that the computational problem to find the maximum weight of an edge-cut is polynomially solvable for the instances G w where G is a graph embedded on an arbitrary fixed orientable surface and the weight function w has only a bounded number of different values. We also survey the related results concerning a duality of the Tutte polynomial and present an application for the weight enumerator of a binary code. In a continuation of this paper which is in preparation we present an application to the Ising problem of three-dimensional crystal structures. Mathematical Reviews Subject Numbers 05B35 05C15 05A15 Supported by NATO-CNR Fellowship y Supported by DONET GACR 0194 and GAUK 194 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R7 1 1 Introduction This is a continuation of our paper A Theory of Pfaffian Orientations I Perfect Matchings and Permanents . We present a new combinatorial way to compute the generating functions of T-joins and k-cuts of graphs. A graph is a pair G V E where V is a set and E is a set of unordered pairs of elements of V. The elements of V are called vertices and those of E are called edges. If e xy is an edge then X y are called endvertices of e. In this paper V will always be finite G V E will always be a graph and xe will be a variable associated with each edge e of G. We let X xe e 2 E denote 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.