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


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

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

Start with a spanning tree and consider the graphs you get by adding a single edge of your graph.



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