Path: utzoo!attcan!uunet!decwrl!ucbvax!MATH.UCLA.EDU!dgc From: dgc@MATH.UCLA.EDU ("David G. Cantor") Newsgroups: comp.theory Subject: Re: Shannon's Switching Game Message-ID: <9006011827.AA05699@irt.watson.ibm.com> Date: 1 Jun 90 18:27:49 GMT References: <88200006@uicbert.eecs.uic.edu> Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: "David G. Cantor" Organization: UCLA Department of Mathematics Lines: 45 simonson@uicbert.eecs.uic.edu In article <88200006@uicbert.eecs.uic.edu> simonson@uicbert.eecs.uic.edu writes: In Shannon's Swithching game, two players alternately choose edges of a given undirected graph until all the edges are chosen. There are two distinguished vertices in the graph, u and v. The goal of one player is to connect these two vertices and the goal of the other player is to separate them. It is known that the "connecting" player can always win if there are two edge disjoint spanning trees of the graph. Does anyone know an algorithm for determining whether a given undirected graph has two edge disjoint spanning trees? If this result is well known, is it a special case of a larger theory? and if such an algorithm exists, and one determines that a given graph has two edge disjoint spanning trees, then is it easy to find them? ------------------------------------------------------------------------ The answer to all of the questions is YES. This is a result in matroid theory. Some references are: 1. Alfred Lehman, "An Introduction to Matroid Theory", SIAM J. 12 (1964), pp 687-725. 2. John Bruno and Louis Weinberg, "A Constructive Graph-Theoretic Solution of the Shannon Switching Game", J. IEEE Trans. Circuit Th. CT-17 (1970), pp 74-80. 3. W. J. Tutte, "Lectures on Matroids", J. of Research of the National Bureau of Standards 69B (1973), pp 1-77. Lehman was the original "solver" of this game. Unfortunately, none of the above references is comprehensible. The standard texts on Matroid Theory generally don't give the solution but refer the reader to one of these three texts. dgc David G. Cantor Department of Mathematics University of California at Los Angeles Internet: dgc@math.ucla.edu