From: hal9000@hypermetrics.com Subject: Graph theory: Classic (simple) problems? Date: Fri, 01 Dec 2000 20:15:13 GMT Newsgroups: sci.math Summary: [missing] Hello... got a question for you guys. Please feel free to correct any ignorance on my part, as I am not a mathematician. I'm looking for simple, classic problems in graph theory -- for example, questions you might want to ask about a graph (or problems you want to solve). This includes directed and undirected graphs and weighted graphs, but not trees necessarily. What I have so far is this: 1. Is there an Euler circuit? (Is "unicursive" the word?) 2. Can it be drawn in a plane? (Doesn't this mean: Does it contain K(4,3)?) 3. Traveling salesman problem 4. Determining connectedness of an adjacency matrix 5. Finding cliques in an adjacency matrix 6. Is it acyclic? Thanks, Hal -- Hal Fulton Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: crankyho Subject: Re: Graph theory: Classic (simple) problems? Date: Fri, 01 Dec 2000 20:39:50 GMT Newsgroups: sci.math Here's a classic problem: Let G be a graph. A clique is a subgraph in which every two vertices are connected by an edge. An anti-clique (or independent set), is a subgraph in which every two vertices are not connected by an edge. Prove that every graph with k vertices contains either a clique or an anti-clique with at least (1/2)*log_2_(k) vertices. l8r, mike Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Steve Lord Subject: Re: Graph theory: Classic (simple) problems? Date: Fri, 1 Dec 2000 18:23:25 -0500 Newsgroups: sci.math On Fri, 1 Dec 2000 hal9000@hypermetrics.com wrote: > Hello... got a question for you guys. > > Please feel free to correct any ignorance on my part, as I am not > a mathematician. > > I'm looking for simple, classic problems in graph theory -- for example, > questions you might want to ask about a graph (or problems you want to > solve). Okay ... > This includes directed and undirected graphs and weighted graphs, but > not trees necessarily. > > What I have so far is this: > > 1. Is there an Euler circuit? (Is "unicursive" the word?) Eulerian circuit? One of the theorems in one of my discrete math books is: There is an eulerian circuit in a finite connected graph if and only if all its vertices have even degree. [Truss, Discrete Mathematics for Computer Scientists, 2nd Edition, ISBN 0-201-36061-6, page 357] > 2. Can it be drawn in a plane? (Doesn't this mean: Does it > contain K(4,3)?) I think you mean K_{3,3} or K_5. Kuratowski proved in 1930 that any non-planar graph must contain one of these two or a subdivision (splitting one or more of the edges in half by adding an extra node in the middle of the edge) thereof. > 3. Traveling salesman problem Tough tough problem. > 4. Determining connectedness of an adjacency matrix That one sounds like it might be interesting. You can do this by adding together powers of the adjacency matrix (where 'addition' is defined as ORing the numbers) and figuring out if the entire matrix becomes filled with 0's. > 5. Finding cliques in an adjacency matrix > 6. Is it acyclic? Sound like interesting problems. Steve L ============================================================================== From: euclid2000@my-deja.com Subject: Re: Graph theory: Classic (simple) problems? Date: Sat, 02 Dec 2000 11:34:16 GMT Newsgroups: sci.math In article <9090sb$p85$1@nnrp1.deja.com>, hal9000@hypermetrics.com wrote: > Hello... got a question for you guys. > > Please feel free to correct any ignorance on my part, as I am not > a mathematician. > > I'm looking for simple, classic problems in graph theory -- for example, > questions you might want to ask about a graph (or problems you want to > solve). > > This includes directed and undirected graphs and weighted graphs, but > not trees necessarily. > Hi IBM, The compound matrix of the adjacency matrix gives the entire set of matchings in a bigraph. For details see K.K. Nambiar: Hall's Theorem and Compound Matrices, Mathematical and Computer Modelling, Vol. 25, No. 3, 1997, pp. 23-24. Cheers euclid > What I have so far is this: > > 1. Is there an Euler circuit? (Is "unicursive" the word?) > 2. Can it be drawn in a plane? (Doesn't this mean: Does it > contain K(4,3)?) > 3. Traveling salesman problem > 4. Determining connectedness of an adjacency matrix > 5. Finding cliques in an adjacency matrix > 6. Is it acyclic? > > Thanks, > Hal > > -- > Hal Fulton > > Sent via Deja.com http://www.deja.com/ > Before you buy. > Sent via Deja.com http://www.deja.com/ Before you buy.