Graph CountingProblem code: GRAPHCT |
All submissions for this problem are available.
First for some definitions :
Let G = (V,E) be an undirected graph containing an edge e = (u,v) with u ? v. Let f be a function which maps every vertex in V\{u,v} to itself, and otherwise, maps it to a new vertex w. The contraction of e results in a new graph G? = (V?,E?), where V? = (V\{u,v})?{w}, E? = E\{e}, and for every x ? V, x? = f(x) ? V? is incident to an edge e? ? E? if and only if, the corresponding edge, e ? E is incident to x in G.
An undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G.
A graph is connected if there exists a path between any two vertices. A biconnected graph is one which remains connected even after the removal of any one vertex and all edges incident to it.
A simple graph is one which does not have more than one edge between any pair of vertex, nor does it have an edge from a vertex to itself.
You need to count how many simple biconnected graphs having n vertices and m edges exist such that they do not have a cycle of length 5 as a minor. Two graphs are considered distinct if there exist vertices having labels i and j which are adjacent in the first graph, but not in the second graph.
Input :
The first line contains the number of test cases T. Each of the next lines contains two integers n and m.
Output :
Output T lines, one corresponding to each test case. For a test case, output the number of graphs as described in the question. Output the answer modulo 1000000007.
Sample Input : 5 1 0 3 2 3 3 4 4 5 10
Sample Output : 1 0 1 3 0
Constraints : 1 <= T <= 2000 1 <= n <= 100 0 <= m <= 10000
| Author: | syco |
| Date Added: | 9-04-2010 |
| Time Limit: | 2 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
n = 4, m = 4 => only one
n = 4, m = 4 => only one biconnected graph is possible so how come the answer is 3 for this case?
just to be clear - two graphs are considered to be distinct if they are non isomorphic ?
Read the last sentence before
Read the last sentence before 'Input'.
what is the meaning of this
what is the meaning of this notation :'V{u,v} ' or 'E{e}' ?
The edge contraction
The edge contraction description is a little hard to understand. Is it just deleting the edge between two vertices and merging the vertices together into one vertex that has both the vertices' adjacencies? That would sound like the standard definition
Edge contraction definition
Edge contraction definition is not clear to me. I can understand Tedrick said. Is that what is meant the normal edge contraction?
Can any1 explain in short wat
Can any1 explain in short wat we have to do??. ... i dont know a s*** abt this f***in graph theory ... :(
All definitions in the
All definitions in the problem statement are standard definitions. Though they are clearly defined, if you don't understand them you could try Wikipedia for more details on what the words mean. Biconnected, simple graph, minor, cycle, isomorphic all have pages on Wikipedia for you to read.
"they do not have a cycle
"they do not have a cycle of length 5 as a minor"
means :
the graph can have a cycle, but the length of the cycle must be <= 5 .
right ?
It means exactly what it says
It means exactly what it says according to the definition of a minor. Any further implications on what this means in the graph is part of solving the problem, do not discuss that.
Does cycle mean cycle with
Does cycle mean cycle with repeated vertices or not ? Admin please clarify .
There is only one definition
There is only one definition of a cycle. http://en.wikipedia.org/wiki/Cycle_graph
Thanks stephen, actually I
Thanks stephen, actually I was referring to http://en.wikipedia.org/wiki/Cycle_(graph_theory) . Hence the confusion .
what is the meaning of this
what is the meaning of this line "they do not have a cycle of length 5 as a minor" can anyone explain the given test case
4 4
how it is 3?
All of those words are
All of those words are clearly defined in the problem statement - what part don't you understand?
@stephen can you please
@stephen can you please explain the result for 4 4, I need one example to undestand. I read all the definitions. but i didn't understand the test case 4 4. :( what are the 3 graphs?
The graphs with vertices 1,
The graphs with vertices 1, 2, 3, 4 have these edges:
a) 1-2, 1-4, 2-3, 3-4
b) 1-2, 1-3, 2-4, 3-4
c) 1-3, 1-4, 2-3, 2-4
if i named 2 by 3 and 3 by 2.
if i named 2 by 3 and 3 by 2. for (c) the it is identical to (a).
So what? The problem
So what? The problem statement says:
Two graphs are considered distinct if there exist vertices having labels i and j which are adjacent in the first graph, but not in the second graph.