Wikipedia:Reference desk/Archives/Mathematics/2010 December 28
| Mathematics desk | ||
|---|---|---|
| < December 27 | << Nov | December | Jan >> | December 29 > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
December 28
[edit]Acyclic Undirected Graph
[edit]Is there a way to tell if an undirected graph is acyclic (or cyclic) based on the properties of its adjacency matrix? I know some linear algebra, but I am new to graph theory. Thanks in advance.
--Russoc4 (talk) 01:47, 28 December 2010 (UTC)
- In a very literal sense, yes - the matrix contains all necessary information to run a cycle search algorithm. However, if I get the gist of your question, you want to know if a property of the matrix that is typically used in linear algebra relates to cycles in the graph. A graph is cyclefree when the number of connected components (c) and edges (e) is equal to the number of nodes (n): n = c + e. The number of nodes is the dimension of the adjacency matrix, the number of edges is half of the total sum of all matrix elements. For the number of connected components, there is an obscure connection to linear algebra in the Laplacian matrix, but nothing more direct comes to my mind. —Preceding unsigned comment added by 94.220.87.6 (talk) 04:26, 28 December 2010 (UTC)
- Is it enough to say acyclic graphs have more nodes than edges? (or as you say, half the number of edges, I assume because the matrix is symmetrical and visually redundant) --Russoc4 (talk) 03:07, 29 December 2010 (UTC)
- You have to account for the number of connected components, as 94.220.87.6 noted above. For a simple example, imagine a graph consisting of a cycle and a bunch of isolated vertices—such a graph has more vertices than edges, but is not acyclic. However, if you know the graph is connected, then it is acyclic if and only if the number of edges is less than the number of vertices. See tree (graph theory) for more information; a tree, which always has n − 1 edges, minimizes the number of edges in a connected graph on n vertices, and so any connected graph on n vertices having n or more edges is not a tree and thus has a cycle. —Bkell (talk) 03:28, 29 December 2010 (UTC)
- The graphs I'm dealing with are connected. Thanks for your help! --Russoc4 (talk) 01:40, 31 December 2010 (UTC)
- You have to account for the number of connected components, as 94.220.87.6 noted above. For a simple example, imagine a graph consisting of a cycle and a bunch of isolated vertices—such a graph has more vertices than edges, but is not acyclic. However, if you know the graph is connected, then it is acyclic if and only if the number of edges is less than the number of vertices. See tree (graph theory) for more information; a tree, which always has n − 1 edges, minimizes the number of edges in a connected graph on n vertices, and so any connected graph on n vertices having n or more edges is not a tree and thus has a cycle. —Bkell (talk) 03:28, 29 December 2010 (UTC)
- Is it enough to say acyclic graphs have more nodes than edges? (or as you say, half the number of edges, I assume because the matrix is symmetrical and visually redundant) --Russoc4 (talk) 03:07, 29 December 2010 (UTC)
The cyclomatic number tells you that. It's a matter of simple arithmetic to know how many cycles an undirected graph has. Given a connected graph G, the cyclomatic number of G, denoted by μ(G), is given by the number of edges, minus the number of vertices, plus one: μ(G) = #V – #E + 1. It is true that
- μ(G) ≥ 0,
- μ(G) = 0 if and only if G is a tree.
In terms of homology theory, the cyclomatic number tells you the rank of the first homology group. In particilar μ(G) = Rank( H1(G,Z) ). — Fly by Night (talk) 02:12, 31 December 2010 (UTC)
- Hmmm. I think you mean #E-#V+1=0 for a tree, but thanks for the info. --Russoc4 (talk) 01:13, 3 January 2011 (UTC)