Carl Love

Carl Love

24673 Reputation

25 Badges

10 years, 58 days
Natick, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

@Deeshani Your expression has unbalanced parentheses. You also have numerous unnecessary pairs of parentheses. Although not erroneous, they only make it more confusing and difficult to correct. You can't correct unbalanced parentheses by adding pairs of parentheses.

@Cata I think that your way is better in this case. My way is more general, but is not as clear.

@lcz Here is the revised edge-contraction procedure. Surprisingly, it's simpler than the original.

Contract:= proc(G::Graph, e::And(set({string, symbol, integer}), 2 &under nops))
description "Remove edge from G by combining end vertices. Output is weighted.";
uses GT= GraphTheory;
local 
    V:= GT:-Vertices(G), n:= nops(V), J:= table(V=~[$n]), 
    W:= GT[`if`(op(2,G)=':-weighted', WeightMatrix, AdjacencyMatrix)](G), 
    u:= J[e[1]], v:= J[e[2]], R:= [1..v-1, v+1..n]
;
    try if W[u,v]=0 then error fi catch: error "edge %1 not found", e end try;
    W[u]+= 2*W[v]; W[u,u]:= 0; 
    GT:-Graph(V[R], rtable(symmetric, W[R,R]))
end proc
:
GT:= GraphTheory:
g:= GT:-ConvertGraph("O~tIID@wL~j`PbOqgLJ@p");
g1:= Contract(Contract(g, {1,3}), {5,6});
plots:-display(GT:-DrawGraph~(<g | g1>));
GT:-MaxFlow(g1,1,4)[1];

 

@lcz For our immediate purpose here (computing MaxFlow), we can use weighted edges to simulate multiple edges. Each original pair of edges through a deleted vertex results in a combination of 2 or 3 edges in the final graph, for which we can use weights 2 or 3. To see that it's possibly 3, consider contracting edge {1,3} from the graph 

g:= GraphTheory:-Graph({[{1,2}, 1], [{1,3}, 1], [{2,3}, 1]});

with 3 being the removed vertex. The resulting graph should be

g1:= GraphTheory:-Graph({[{1,2}, 3]});

I will rewrite Contract to do its work by addition of rows and columns of the weight matrix, which I'll construct if needed (using MakeWeighted, of course), followed by deletion of a row and a column. The weight matrix and vertex list are sufficient for the Graph command. I include the vertex list so that the vertices don't get renumbered, which would cause confusion for the user.

It's clear that the following sentence (excerpted from the passage that I quoted above) in the paper is incorrect:

  • Then, each edge is replaced by two oppositely directed arcs, the capacity of each arc is set to unity. 

The "unity" is incorrect. And Maple doesn't require us to use a pair of arcs instead of an edge, although some other software likely does.

@DSP514 The colons and semicolons are statement separators. The colon suppresses the display of the final result of the statement that precedes it; the semicolon does not suppress it. 

@bstuan "Exactly when" is poor phrasing. "If and only if" would be better. So, don't fret about not understanding it at first.

@bstuan The theorem you just posted states "int(f(x), x= a..b) converges exactly when int(g(x), x= a..b) converges." That means that they either both converge or both diverge. For your problem, they both diverge.

@bstuan The limit being 2 is fine for proving divergence. See https://math.uchicago.edu/~tghyde/LimitComparison.pdf

@bstuan You wrote:

  • My mistake! Sorry for my incorrect word usage.I often use the word "Convergence" to generally refer to the convergence or non-convergence (divergence) of a series or a improper integral.

I think that your original phrasing "convergence property of the following improper integral can be checked by the comparison method" is understandable.

@tomleslie The OP needs to find a function g(x) such that 

  • there exists an a > 0 such that 0 <= g(x) <= f(x) for all x in the open interval 0 < x < a,
  • g(x) has an easy-to-find antiderivative,
  • int(g(x), x= 0..a) = infinity,

in order to prove that int(f(x), x= 0..1) diverges (by comparison test).

Here is a procedure to do a single edge contraction:

Contract:= proc(G::Graph, e::And(set({string, symbol, integer}), 2 &under nops))
description "Remove an edge from G by combining its end vertices.";
uses GT= GraphTheory;
local 
    V:= GT:-Vertices(G), n:= nops(V), J:= table(V=~[$n]), E:= rtable(op(4,G)), 
    u:= J[e[1]], v:= J[e[2]], P:= v+1..n, R:= [1..v-1, P]
;
    E[u]:= (E[u] union E[v]) minus {u,v};
    GT:-Graph(V[R], subsindets(subs(v= u, E[R]), integer[P], `-`, 1))
end proc
:
GT:= GraphTheory:
G:= GT:-SpecialGraphs:-PetersenGraph():
GT:-Edges(G)[1];
                             {1, 2}
G1:= Contract(G, {1,2});
G1 := Graph 10: an undirected unweighted graph with 9 vertices and 14 edge(s)

plots:-display(GT:-DrawGraph~(<G | G1>));

Since we're always going to do two edge contractions, some efficiency can be had by doing them both at once. But I'd rather finish the algorithm first and come back to that later.

@lcz This passage from page 197 of the paper that you referenced explains how to reduce the computation of to a max-flow problem. This is also what I would've come up with myself.

  • We shall show that M(e_i, e_j) for a given pair of independent edges e_i and e_j can be computed by solving a network flow problem.
    We proceed with the computation of M(e_i, e_j). Let e_i = (u, v) and e_j = (x, y). Note that the endvertices u, v, x, and y are all distinct as we are assuming that e_i and e_j are independent edges in G. Now, contract the edge e_i in G by identifying its endvertices u and v to obtain a single vertex called s. Do the same thing for edge e_j and call the corresponding vertex t. The resulting graph will be referred to as G’. We now define a network graph N from G’ by letting vertex s be its source and vertex t be its sink. Then, each edge is replaced by two oppositely directed arcs, the capacity of each arc is set to unity. It is not difficult to see that the value of a max-flow function in network N is equal to M(e_i, e_j) in graph G.

What is the real-valued function M used in the algorithm's pseudo-code? And what is the set-valued function I? I guess that I(v) is either the set of edges connected to v or not connected to v. I have no guess for M.

@rockyicer As you likely realize, what you're currently asking about has nothing to do with the mathematical aspects of the solution. Rather, I did it solely for the display aspect, to put the variables back the way that you originally had them.

Before I give a more-thorough Answer, tell me which (if any) of these Maple commands you already have a basic understanding of: type, indetssubsindets, cat, op, op(0, ...).

In my command above, patindex(anything) is the type of subexpression to be changed. The pat stands for "patterned" (which I think you figured out already). So, it looks for indexed expressions with a certain type pattern in the indices. But, since I specifed anything, it'll match any indexed expression. So, I could've (and for sake of simplicity, I should've) used indexed instead of patindex(anything). See the help pages ?type, ?type,structure (for patindex), ?type,anything, ?indexed, ?type,indexed.

Supposed that n is an indexed name, for example n = x[1,2]. Then op(0, n) = x, op(n) = (1, 2), and op(0.., n) = (x, 1, 2). (There's a distinction between indexed and subscriptedSubscripted refers to the form of typographic display of an expression, but indexed refers to its internally stored structure.) The op stands for "operands". It's the most-fundamental Maple command for deconstructing expressions. See ?op and ?name.

The cat stands for "catenate". It's the Maple command for building symbols and strings. So, using the same n as above, the cat command becomes cat(x, (1, 2)) ==> cat(x, 1, 2) ==> x12. See ?cat.

Regarding the length and complexity of my command: It could be replaced with

S:= simplify(solve(Eqs, Svars));  #Do the algebra.
subsindets[2](S, indexed, 0.., cat@op);  #Do the typography.

The [2] after subsindets causes the indexed subexpressions to be passed as the 2nd argument to the transformer, cat@op, with 0.. being its (constant) 1st argument. See ?subsindets.

@nm You're right about the right directional limit, but I have some doubt left about the leftlimit(ln(x)/x, x= 0, left) returns infinity. I expected (1 - I)*infinity.

2 3 4 5 6 7 8 Last Page 4 of 641