| (9 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
Has anyone found a method for counting the number of subgraphs of W3 without actually drawing out every graph and counting them?<br> --[[User:Aoser|Aoser]] 16:51, 3 November 2008 (UTC) | Has anyone found a method for counting the number of subgraphs of W3 without actually drawing out every graph and counting them?<br> --[[User:Aoser|Aoser]] 16:51, 3 November 2008 (UTC) | ||
| − | -- | + | ---- |
| − | Yep, I found. Build the adjacency matrix for W3.<br> 1) Consider (# ways to choose i vertices), where i=1,2,3,4.<br> 2) Also consider # places for edges in each configuration (with 1, 2, 3, 4 vertices) - build the edge or not (2 choices).<br> Combine these using product & sum rules.<br> Hope it helps<br>--[[User:Asuleime|Asuleime]] 22:45, 5 November 2008 (UTC) | + | Yep, I found. Build the adjacency matrix for W3.<br> 1) Consider (# of ways to choose i vertices), where i=1,2,3,4.<br> 2) Also consider # of places for edges in each configuration (with 1, 2, 3, 4 vertices) - build the edge or not (2 choices).<br> 3) Combine these using product & sum rules of counting.<br> Hope it helps<br>--[[User:Asuleime|Asuleime]] 22:45, 5 November 2008 (UTC) |
| + | |||
| + | ---- | ||
| + | |||
| + | I also thought of another way of doing this. Draw the graph with all the edges. (It should be a triangle with another vertex in the center, all connected.) Counting the edges, there are 6. Consider every edge to be a binary function of either on or off, therefore there are 2^6 - 1 ways when you subtract the null value graph. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | But then you don't count the subgraphs with isolated vertices. My answer is (4 choose 1) + (4 choose 2)*(2^1) + (4 choose 3)*(2^3) + (4 choose 4)*(2^6). Try it.<br> | ||
| + | --[[User:Asuleime|Asuleime]] 14:17, 6 November 2008 (UTC) | ||
| + | ---- | ||
| + | |||
| + | The easiest way I think is to split it into cases where 4 vertices remain, 3 vertices remain... 1 vertex remains. It may seem like you are doing 4 times as much work, but if you know how many vertices remain, the problem becomes easy in each case. (See explanation above) | ||
| + | --[[User:Norlow|Norlow]] 18:09, 8 November 2008 (UTC) | ||
Latest revision as of 13:09, 8 November 2008
Has anyone found a method for counting the number of subgraphs of W3 without actually drawing out every graph and counting them?
--Aoser 16:51, 3 November 2008 (UTC)
Yep, I found. Build the adjacency matrix for W3.
1) Consider (# of ways to choose i vertices), where i=1,2,3,4.
2) Also consider # of places for edges in each configuration (with 1, 2, 3, 4 vertices) - build the edge or not (2 choices).
3) Combine these using product & sum rules of counting.
Hope it helps
--Asuleime 22:45, 5 November 2008 (UTC)
I also thought of another way of doing this. Draw the graph with all the edges. (It should be a triangle with another vertex in the center, all connected.) Counting the edges, there are 6. Consider every edge to be a binary function of either on or off, therefore there are 2^6 - 1 ways when you subtract the null value graph.
But then you don't count the subgraphs with isolated vertices. My answer is (4 choose 1) + (4 choose 2)*(2^1) + (4 choose 3)*(2^3) + (4 choose 4)*(2^6). Try it.
--Asuleime 14:17, 6 November 2008 (UTC)
The easiest way I think is to split it into cases where 4 vertices remain, 3 vertices remain... 1 vertex remains. It may seem like you are doing 4 times as much work, but if you know how many vertices remain, the problem becomes easy in each case. (See explanation above) --Norlow 18:09, 8 November 2008 (UTC)
