Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A note on random minimum length spanning trees"

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: A note on random minimum length spanning trees. | A note on random minimum length spanning trees Alan Frieze Miklos Ruszinkct Lubos Thoma Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA15213 UsA alan@random.math.cmu.edu ruszinko@lutra.sztaki.hu thoma@qwes.math.cmu.edu Submitted June 28 2000 Accepted August 11 2000 Abstract Consider a connected r-regular n-vertex graph G with random independent edge lengths each uniformly distributed on 0 1 . Let mst G be the expected length of a minimum spanning tree. We show in this paper that if G is sufficiently highly edge connected then the expected length of a minimum spanning tree is nc 3 . If we omit the edge connectivity condition then it is at most n c 3 1 . 1 Introduction Given a connected simple graph G V E with edge lengths x xe e 2 E let mst G x denote the minimum length of a spanning tree. When X Xe e 2 E is a family of independent random variables each uniformly distributed on the interval 0 1 denote the expected value E mst G X by mst G . Consider the complete graph Kn. It is known see 2 that as n 1 mst Kn 3 . Here 3 ịj3 1.202. Beveridge Frieze and McDiarmid 1 proved two theorems that together generalise the previous results of 2 3 5 . Supported in part by NSF Grant CCR9818411 email alan@random.math.cmu.edu 1 Permanent Address Computer and Automation Research Institute of the Hungarian Academy of Sciences Budapest P.O.Box 63 Hungary-1518. Supported in part by OTKA Grants T 030059 and T 29074 FKFP 0607 1999. email ruszinko@lutra.sztaki.hu Supported in part by NSF grant DMS-9970622. email thoma@qwes.math.cmu.edu 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R41 2 Theorem 1 For any n-vertex connected graph G mst G A c 3 - 61 where A A G denotes the maximum degree in G and 61 61 A 0 as A 1. For an upper bound we need expansion properties of G. Theorem 2 Let a a r O r-1 3 and let p p r and r tend to infinity with r. Suppose that the graph G V E is connected and satisfies r s A 1 a r 1 where s S G denotes the minimum degree in G. Suppose