Tag Info

Hot answers tagged

8

From what I understand there are broadly two distinct applications of mathematics to neuroscience. One uses mathematics to study the biological/chemical/physical aspects of the mechanisms in the brain, such as action potentials and the interactions between neurons. The type of math used here is differential equations/dynamic systems. Relevant wikipedia ...


4

Well spotted. In a case like this, it's a good idea to check the article's history (using the "View history" link at the top). In the present case, the error was introduced only two days ago by an anonymous user in this edit (which I just reverted).


4

These notes contain a proof. The digraph used in this proof is a little more complicated than the one that you have in mind: each point of the partial order corresponds to two vertices of the digraph. Let $\langle P,\preceq\rangle$ be the partially ordered set; I’ll write $p\prec q$ to indicate that $p\preceq q$ and $p\ne q$. For each $p\in P$ the digraph ...


4

Imagine a complex pipeline with a common source and common sink. You start to pump the water up, but you can't exceed some maximum flow. Why is that? Because there is some kind of bottleneck, i.e. a subset of pipes that transfer the fluid at their maximum capacity--you can't push more through. This bottleneck will be precisely the minimum cut, i.e. the set ...


3

Commonly used models in mathematical physics for collections of neurons are so-called neural networks. Here is some general explanation of the models. Some popular models are the Hopfield model, Ashkin-Teller neural networks, Blume-Emery-Griffiths neural networks,... Techniques used to solve them involve statistical mechanics which result in partition ...


3

Probably you'll find this one very useful. Chapter 5 ($M/M/C$ queue) corresponds to your model, where it is assumed that there are $c$ servers, the service time is exponentially distributed, and so are the interarrival times (of course, with different means). Anyway, the key is $M/M/C$ (or $M/M/N$, etc.) queue.


3

A side remark: it is called a skew-symmetry, because of the minus sign (source). Also, your third rule should be $$\sum_{v \in V} f(u, v) = 0, \quad \text{for all $u \in V \setminus \{s,t\}$},$$ because the flow between each vertex and start/target one should also be considered in the sum (see my explanation of the conservation of flow a bit lower), but it ...


2

Everything regarding the question should be clear from the Wikipedia entry you referred to. Anyway, flow networks are directed graphs by definiton. For 'skew symmetry' Cormen's Introduction to Algorithms says: Skew symmetry is a notational convenience that says that the flow from a vertex $u$ to a vertex $v$ is the negative of the flow in the reverse ...


2

There are no graphs for which the Tutte polynomial is $0$. One thing that would go wrong if there were such a graph: The chromatic polynomial is contained within the Tutte polynomial; if the Tutte polynomial were $0$, then the graph would not be $k$-colourable for all $k \geq 0$. But this is impossible since e.g. we can colour each vertex a different ...


2

Hint: Create $G'$ as follows: For any $w \in V$ create two vertices $w_\text{in}$ and $w_\text{out}$. Connect them with an edge of zero cost. For any $e \in E$ create two vertices $e_\text{in}$ and $e_\text{out}$. Connect them with an edge of zero cost. For any $e = (w \to w') \in E$ add edges $\{w_\text{out},e_\text{in}\}$ and $\{e_\text{out}, ...


2

The network in (b) shows the situation after deletion of the $(s^*, t^*)$ arc. The $(s^*, t^*)$ arc needs to be removed in order to have a one-to-one correspondence between $s$-$t$ cuts in the primal and paths from $s^*$ to $t^*$ in the dual. No, it doesn't belong to the dual network. Dual arcs must be between faces in the primal network. I'm not sure ...


2

First of all, the algorithm terminates because at least one edge is saturated in each step and there is a finite number of edges. Now let $f$ be the resulting flow, and assume $f'$ is some greater flow through the tree. For $f'$ to be a greater flow than $f$, we must have $f'(e)\gt f(e)$ for at least one edge $e$ leading away from the source. Now ...


2

Each of the basic flows you're using should conserve flow at nodes other than s and t. For convenience, write e.g [acba] as a flow of 1 unit on the cycle $a \to b \to c \to a$, and [sat] as 1 unit on $s \to a \to t$. So you could end up with something like $\frac{3}{2} [sat] + 2 [acba] + [abta]$ (just for illustration; that's not the answer here)


2

The trick would be to separate a vertex $v$ into two new vertices $v^-$ and a $v^+$ in. In a directed graph you then connect all incoming edges to $v$, denoted $\delta^-(v)$, to $v^-$ and all outgoing edges, denoted $\delta^+(v)$ to $v^+$. Finally, you add an edge from $v^-$ to $v^+$ with capacity equal to the capacity the vertex $v$ originally had. This way ...


2

I will try to show you why this is intuitive using counter example. Let us call the set reachable by unsaturated paths A, and the other set B. so s is in A, and t is in B. We know that by definition, each edge from A to B is in the minimum cut. Now suppose A were some other set such that it had a node v such that v was not reachable by an unsaturated path. ...


2

What you're looking for is described on pages 247-249 of Robert Vanderbei's Linear Programming: Foundations and Extensions (2nd edition), although Vanderbei has some of his sign conventions opposite of yours. Take a close look in particular at Figure 14.4 on page 249 ("Adding a new node to accommodate an arc $(i,j)$ having an upper bound $u_{ij}$ on its ...


1

May I recommend you these lectures of Anupam Gupta? Lecture 19: Sparsest Cut Lecture 20: Embeddings into Trees and L1 Embeddings The first one will guide you through understanding the relation of sparsest cut approximations and metric embeddings, and the second will give you an idea on how to embed arbitrary finite metric spaces into $l_1$ with low ...


1

http://www.seas.upenn.edu/~deepc/Courses/CIS800/Notes/lec8.pdf look at ckr algo for finding a multi-cut. Theorem 2 state that this cut is no bigger then logn from min fractional cut which is equal to the max flow.


1

Put it each column the corresponding variable, last column is used for constants. So rewrite each equation in the form $...=0$. Then, for $A$ we get $x_1-x_2+x_4=0$, $B$: $x_2-x_3-100=0$, $C$: $x_3-x_4+80=0$. Put that in a matrix: $ \begin{pmatrix} 1 & -1 & 0 & 1 & 0\\ 0 & 1 & -1 & 0 & -100\\ 0 & 0 & 1 & -1 & ...


1

I am not sure I understand your question. The sparsest cut is a node set $S \subseteq V$ that minimizes the "sparcity" measure: $$\Phi(S) = \frac{c(S, \bar{S})}{D(S, \bar{S})},$$ where $c(S, \bar{S})$ is the sum of the capacities of the edges having one endpoint in $S$ and the other in $\bar{S}$, and $D(S, \bar{S})$ is the demand from $S$ to $\bar{S}$. ...


1

Actually, you understand more than you think :). The proof indeed goes by contradiction, in that if the optimal cut induced disconnected components, then one of the components would give a better cut value. The rest of the proof follows from the fact that you can now parametrize the set of candidate optimal solutions by edges from the tree (since each edge ...


1

Try this: let $e$ join $v$ to $w$, delete every edge that is neither in a path from source to $v$ nor in a path from $w$ to sink, and find a maximal flow in what's left of the network. EDIT: Here's another way to achieve this. Reviewing the notation: the source is $s$, the sink is $t$, the edge $e$ joins $u$ to $v$. Make believe the sink is $u$, and find a ...


1

A maximum flow is a flow that attains the highest flow value possible for the given network. A maximal flow is a flow whose value cannot be increased without decreasing the flow along some arc. All maximum flows are maximal flows. Not all maximal flows are maximum flows. Figure 3.9 in the Bang-Jensen and Gutin textbook, first edition illustrates an ...


1

Instead of constructing $V^\prime$ so that the edges $(u, v) \in E$ have capacity $1$, let such $(u,v)$ have infinite capacity and the edges $(s,u)$ and $(v,t)$ have capacity $1$. Then an integral flow (and there must be a maximum flow which is integral) can send at most one unit of flow through each $u\in V_1$ and $v \in V_2$, and one can tell which ...


1

Showing (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i) is sufficient. So, you can prove (i) $\Rightarrow$ (ii) by contraposition, NOT (ii) $\Rightarrow$ NOT (i). That is, suppose $T$ doesn't have the cut property. Then you can find $e' \notin T$ in a cut defined by some $e \in T$ such that $c(e') < c(e)$. But adding $e'$ to $T$ creates ...


1

Your five equations are correct. The sixth equation is $x_1=x_2+x_4$. You'll then have six linear equations in seven real unknowns, which is not enough to find a unique solution. Question (a) is very vague, since no unique solution exists. Perhaps what is being asked is a list of the six equations. Or perhaps you can choose a variable, say $x_1$, and ...


1

There seems to be some small confusion here. Your primal is the path-flow formulation of the multicommodity flow problem, which orders separate path-flow to every path in some given path set $P$ (which in turn can be of exponential size), while your dual is in fact the dual linear program corresponding to the arc-flow formulation (and hence has polynomial ...


1

To relabel (at least in this case) means to permute the labels. The vertices are currently labeled $1$ through $8$; the arcs strictly speaking haven't been labeled but could be regarded to be implicitly labeled $1$ through $7$ in the order in which they're listed. If you write down the incidence matrix with the rows and columns ordered according to these ...


1

Yes, you should increase the capacity of reverse edge by flow sent. Each time sending some flow by edge you should update its reverse edge too, so that flow passes only in one direction and the reverse edge has capacity = initial capacity + flow. http://stackoverflow.com/questions/7687732/maximum-flow-ford-fulkerson-undirected-graph ...


1

You misunderstood the result. Whether a flow is possible or not is not relevant. In your first case, where the graph is $ s \to a \, \ t $ the minimal cut (=partition of the nodes into two sets, one containing s and the other t) is ({s,a}, {t}) which has capacity 0 because there are no edges from one set to the other. The other cut ({s},{a,t}) has ...



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