# Tag Info

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 ...

4

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 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 ... 2 Hints: The minimum will be achieved by the graph consisting of the shortest possible cycle and a bunch of isolated vertices. (There's no condition on the graph being connected.) Assuming we're working with simple graphs, the shortest cycle is the 3-cycle. So K_3 \cup 27K_1 contains the fewest cycles in a graph with a single cycle, drawn below: For ... 1 The minimal polynomial of n \phi is z^2 - n z - n^2, so a graph is "golden" iff its characteristic polynomial is divisible by z^2 - n z - n^2 for some nonzero integer n. 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 ... 1 Presumably \alpha is a positive integer \le n, and this is talking about an edge colouring, not a vertex colouring. Since this is about Probabilistic Methods, colour each edge randomly 0 or 1, independently and with equal probabilities. For any given K_\alpha subgraph, the probability that this is monochromatic, i.e. that all \alpha \choose 2 edges ... 1 Two classes of models: Markov chains of higher order, and Varying Length Markov Chains (VLMCs, also known as Variable-Order Markov Models). 1 Ore's Theorem says let G be a graph of order p and if, for every pair of nonadjacent vertices v and w we have \deg{v}+\deg{w}\ge p, then G is Hamiltonian. You cannot apply this theorem when your 4-regular graph has p=m\cdot n> 8, but that does not mean that it isn't Hamiltonian. Looking at the graph you have defined, it appears it is ... 1 Maybe she is estimating as:$$ || \sum_i a_i \phi_i T^{\frac{1}{2}} || \leq || T^{\frac{1}{2}} || \cdot || \sum_{i \neq 0} a_i \phi_i || \\ \leq || T^{\frac{1}{2}} || \cdot || \sum_{i} a_i \phi_i || \leq || T^{\frac{1}{2}} || \cdot || f T^{-\frac{1}{2}} || \\ \leq || T^{\frac{1}{2}} || \cdot || T^{-\frac{1}{2} } || \cdot || f|| \leq \frac{\max_x ...

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

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

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

The problem you pose seems to be wide open, as indicated in a number of recent publications devoted to it. Even in a special case when a forest is a tree not as much is known. There is a recent conjecture by Haler and Wang: $k$ edge disjoint copies of a tree $T$ on $n$ vertices can be placed in the complete graph if and only if every vertex of $T$ has degree ...

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

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 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

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