Tag Info

Hot answers tagged

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 finite graph G has an even number of vertices, each with odd valency. What the theorem states actually is: A finite 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