# Tag Info

## Hot answers tagged graph-theory

4

This is called the maximum matching problem, and it is one of the few graph problems for which there is a non-obvious polynomial time algorithm! It's called Edmonds's blossom algorithm: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm Edit: Following Casteels's suggestion, here's an example showing that the greedy algorithm might only get you ...

3

Do you have to prove it that way? It is not difficult to prove directly that there is no closed knights tour of a 3 x 8 board. You start with squares that have only two moves available, so you know both those moves must be part of any tour. Label the squares $$\begin{array}{cccccccc}1 & 4 & 7 & 10 & 13 & 16 & 19 & 22\\ 2 & 5 ... 3 Where does it say that a finite graph has an odd valency at each vertex? I see it saying the number of such vertices is even. Note that zero is an even number. There is no contradiction here. 3 The confusion is that you read the theorem the following way: A ﬁnite graph G has an even number of vertices, each with odd valency. What the theorem states actually is: A ﬁnite graph G has an [even number of vertices with odd valency]. Or, to make it more clear: Theorem In a finite graph, the number of vertices which has an odd valency is even. ... 2 Since K_5 contains a 3-cycle and K_{3,3} a 4-cycle, your proposed algorithm fails on any graph that is not planar and has girth at least five, e.g., the Petersen graph. 1 It is quite straightforward to prove formally: Let d be the diameter of the graph, the length of the longest shortest path between two vertices. Let p = \frac{1}{n}, where n is the number of vertices. Let v be an arbitrary vertex. Then at each time point, there is at least a p^d chance of reaching v in \leq d steps (since there is a path from ... 1 If your graph has two vertices of outdegree k and no vertex of outdegree t, the sum of all outdegrees is k+(0+1+\ldots+(n-1)-t). This sum is 0+\ldots+(n-1) for any tournament, so that k=t, a contradiction. 1 Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics) (ISBN-13: 978-3642244872) and Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics) (ISBN-13: 978-3540443896) The first as general introduction and enough for most cases, the latter as reference material covering basically the whole topic 1 I have little to add here, except maybe a verbal description of the automorphisms as they contribute to the cycle index Z(G) of the automorphism group G. Let's do the enumeration one more time. First, there is the identity, contributing a_1^6. There is a flip of the left fork, which gives a_2 a_1^4. Same for the right fork, a_2 a_1^4. ... 1 It seems that the \leq at the end should be \geq. Since the function on the left-hand side is unimodal and is zero when n=0 and n=\infty, the inequality$$ \left(\frac{en}{k}\right)^k e^{-(n-k)/2^k} < 1 $$is satisfied in two intervals of the form n \in [0,a) \cup (b,\infty). Let's consider = instead of < for simplicity. Rearranging ... 1 I think the most natural definition might just be A morphism of relations \alpha\colon R\to R' is a pair (M_1,M_2) of relations M_1\colon X\to X' and M_2\colon Y\to Y' such that R'\circ M_1=M_2\circ R. This definition at least makes the class of relations and morphisms into a category, and your diagram commutes by definition. You could of ... 1 Start with a spanning tree and consider the graphs you get by adding a single edge of your graph. 1 More generally, for an arbitrary graph, you can consider all paths starting at a particular node; this "path space" has some nice properties. By restricting to LOOPS that start and end at some particular node, you get the loopspace of the graph; there's a natural kind of "multiplication" in which you traverse one loop and then the other; the composition ... 1 The result is in fact not true. Suppose there is only one vertex of degree \leq 1. Then since the average degree is less than two, there are no vertices of degree \geq 3. In other words, we have one vertex with degree \leq 1 and all other vertices have degree 2. Since the sum of the degrees in a graph is always even (as it iss twice the number of ... 1 It depends on what you mean by "directly influenced by". For instance, I could take the distribution that always picks a particular vertex p and then a particular vertex q. This doesn't seem to directly reference either their neighbors or degrees. The probability that the two vertices I pick "randomly" are connected by an edge is either 0 or 1 depending of ... 1 If the preliminary tail is length T and the cycle is length C (so in your picture, T=3, C=6), we can label the tail nodes (starting at the one farthest from the cycle) as -T, -(T-1),..., -1 and the cycle nodes 0, 1, 2, ..., C-1 (with the cycle node numbering oriented in the direction of travel). We may use the division algorithm to write ... 1 Two classes of models: Markov chains of higher order, and Varying Length Markov Chains (VLMCs, also known as Variable-Order Markov Models). 1 If the simple graph has 31 edges, the sum of the degrees have to be  2 \times 31 = 62 . Given that there are 3 vertices of degree 1 and 7 vertices of degree 4, the maximum degree of the graph is$$ 3 \times 1 + 7 \times 4 + 3 \times 9 + 3 = 61 . Hence, no such graph exists.

1

The degree sequence (not necessarily in increasing order) of such a graph is $1,1,1,4,4,4,4,4,4,4,a,b,c$. We have $a+b+c=31$ since the sum of the degree sequence must be $62$. Now the vertices with unknown valences are each at most $12$ (since graph is simple). However, each of the degree $1$ vertices allows at most $1$ connection to the unknown vertices. ...

1

I think you mean $w$ is the number of connected component of $T-e$. The proof is simple, since if we remove $e$ and surely $w(T-e)\le d(e)$, since otherwise the graph will not be connected initially, thus not a tree. It's also obvious that $w(T-e)\ge d(e)$, since if $w(T-e)< d(e)$, this implies that two neighbors of $e$ are connected, adding in $e$ ...

1

You can just move the whole stack from Start to 1 to 4 to End in the usual way, using $3(2^n-1)$ steps, so that is an upper bound. Even without nodes 2 and 3 you have additional freedom. You can move the whole stack to node 1 $(2^n-1$ moves), then move all but the last back to start $(2^{n-1}-1$ moves), then move the bottom all the way ($2$ moves). This ...

Only top voted, non community-wiki answers of a minimum length are eligible