Carl Love

Carl Love

26488 Reputation

25 Badges

12 years, 261 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are answers submitted by Carl Love

I think that the following is what you have in mind, although it's not quite correct to say that it's the surface common to the two cylinders. Rather, it's the portion of each cylinder that's inside the other.

plots:-display(
    plot3d(  # y^2 + z^2 = 1:
        [[r, t, sqrt(1-r^2*sin(t)^2)], [r, t, -sqrt(1-r^2*sin(t)^2)]],
        r= 0..1, t= -Pi..Pi, coords= cylindrical
    ),
    plot3d(  # x^2 + y^2 = 1:
        [1, t, z], 
        t= -Pi..Pi, z= -sqrt(1-sin(t)^2)..sqrt(1-sin(t)^2), coords= cylindrical
    ),  
    scaling= constrained, labels= [x,y,z]
);

You seem to be having trouble distinguishing a procedure's input from its output. You want a procedure whose input is the integer dimensions of the matrix and whose output is the matrix itself. 

Matrix01:= proc(m::nonnegint, n::nonnegint:= m)
    Matrix((m,n), (i,j)-> modp(i+j, 2)) 
end proc
:
#Examples:
Matrix01(4);
Matrix01(3,5);

 

A fundamental motivation of the discipline of Combinatorics is that counting combinatorial structures can often be done using far less computational effort than generating the structures. Counting partitions is like that.

It can be done quite efficiently with a very short recursive procedure:

restart:
CountSums:= (k::posint, N::set(posint))->
    ((k,n)-> (thisproc(args):= 
        `if`(k*n > 0, thisproc(k, n-1) + thisproc(k-N[n], n), `if`(k=0, 1, 0))
    ))(k, nops(N))
:  
CodeTools:-Usage(CountSums(1000, {2,3,6,9}));
memory used=421.16KiB, alloc change=0 bytes,
cpu time=15.00ms, real time=7.00ms, gc time=0ns

                             526848
CountSums(9, {2,3,6,9});
                               4
CountSums(8, {2,3,6,9});
                               3
#Verify correctness:
CodeTools:-Usage(combinat:-numbpart(100));
memory used=2.14MiB, alloc change=0 bytes,
cpu time=31.00ms, real time=33.00ms, gc time=0ns

                           190569292

CodeTools:-Usage(CountSums(100, {$100}));
memory used=1.18MiB, alloc change=0 bytes, 
cpu time=16.00ms, real time=13.00ms, gc time=0ns

                           190569292

So, for this example, my procedure's time beats the library procedure combinat:-numbpart.

@Pepini You wrote:

  • I thought about use parametrization of torus:
    plot3d([(R + r*cos(t)*cos(s), (R + r*cos(t)*sin(s), r*sin(t)], t = 0 .. 2*Pi, s = 0 .. 2*Pi)

You are missing some parentheses in that parametrization: The R also needs to be multiplied by the cos(s) or sin(s). That omission may be why your plot wasn't satisfactory as a surface of revolution. Here's a correction:

r:=  t-> 1 + sin(8 + sin(16 + sin(32*t)))/4:  #This works for any polar curve in form r = f(t)
R:= 2:
plot3d(
     [(R + (r*cos)(t))*~(cos,sin)(s), (r*sin)(t)], t= -Pi..Pi, s= -Pi..Pi,
     scaling= constrained,  
#usually a better option than using 'view'
     grid= [101,49]   #Increase points used for t to show wrinkling
);

This is a figure homeomorphic to an ordinary torus, not the "flat torus" that @sand15 gave links to a PDF about and you showed a picture of. And it has only one level and direction of what those authors call "corrugation" (you might call it "wrinkling"). I think that 2 directions would be the minimum for a reasonable plot, but 1 direction is the most that can be accommodated by a surface of revolution. 

Here's a Matrix with all the information you need. You could display it more elegantly with DocumentTools, I suppose.

restart:

interface(rtablesize= [37,11]):

<
    <x, seq(nprintf("%4.2f", j/100), j= 0..9)>^%T,
    <
        <seq(nprintf("%3.1f", i/10), i= 0..35)> |
        Matrix((36,10), (i,j)-> evalf[4]((1+erf((10*i+j-11)/100/sqrt(2)))/2))
    >
>;

Matrix(37, 11, {(1, 1) = x, (1, 2) = `0.00`, (1, 3) = `0.01`, (1, 4) = `0.02`, (1, 5) = `0.03`, (1, 6) = `0.04`, (1, 7) = `0.05`, (1, 8) = `0.06`, (1, 9) = `0.07`, (1, 10) = `0.08`, (1, 11) = `0.09`, (2, 1) = `0.0`, (2, 2) = .5000, (2, 3) = .5040, (2, 4) = .5080, (2, 5) = .5120, (2, 6) = .5160, (2, 7) = .5199, (2, 8) = .5239, (2, 9) = .5279, (2, 10) = .5319, (2, 11) = .5358, (3, 1) = `0.1`, (3, 2) = .5398, (3, 3) = .5438, (3, 4) = .5478, (3, 5) = .5517, (3, 6) = .5556, (3, 7) = .5596, (3, 8) = .5636, (3, 9) = .5675, (3, 10) = .5714, (3, 11) = .5753, (4, 1) = `0.2`, (4, 2) = .5792, (4, 3) = .5832, (4, 4) = .5870, (4, 5) = .5910, (4, 6) = .5948, (4, 7) = .5987, (4, 8) = .6026, (4, 9) = .6064, (4, 10) = .6102, (4, 11) = .6140, (5, 1) = `0.3`, (5, 2) = .6179, (5, 3) = .6217, (5, 4) = .6255, (5, 5) = .6293, (5, 6) = .6330, (5, 7) = .6368, (5, 8) = .6406, (5, 9) = .6443, (5, 10) = .6480, (5, 11) = .6517, (6, 1) = `0.4`, (6, 2) = .6554, (6, 3) = .6591, (6, 4) = .6627, (6, 5) = .6664, (6, 6) = .6700, (6, 7) = .6736, (6, 8) = .6772, (6, 9) = .6808, (6, 10) = .6844, (6, 11) = .6879, (7, 1) = `0.5`, (7, 2) = .6914, (7, 3) = .6950, (7, 4) = .6984, (7, 5) = .7019, (7, 6) = .7054, (7, 7) = .7088, (7, 8) = .7122, (7, 9) = .7156, (7, 10) = .7190, (7, 11) = .7224, (8, 1) = `0.6`, (8, 2) = .7257, (8, 3) = .7290, (8, 4) = .7323, (8, 5) = .7356, (8, 6) = .7389, (8, 7) = .7422, (8, 8) = .7454, (8, 9) = .7486, (8, 10) = .7518, (8, 11) = .7548, (9, 1) = `0.7`, (9, 2) = .7580, (9, 3) = .7612, (9, 4) = .7642, (9, 5) = .7672, (9, 6) = .7703, (9, 7) = .7733, (9, 8) = .7764, (9, 9) = .7793, (9, 10) = .7823, (9, 11) = .7852, (10, 1) = `0.8`, (10, 2) = .7881, (10, 3) = .7910, (10, 4) = .7938, (10, 5) = .7967, (10, 6) = .7995, (10, 7) = .8023, (10, 8) = .8050, (10, 9) = .8078, (10, 10) = .8106, (10, 11) = .8132, (11, 1) = `0.9`, (11, 2) = .8159, (11, 3) = .8186, (11, 4) = .8212, (11, 5) = .8238, (11, 6) = .8264, (11, 7) = .8289, (11, 8) = .8314, (11, 9) = .8340, (11, 10) = .8364, (11, 11) = .8388, (12, 1) = `1.0`, (12, 2) = .8413, (12, 3) = .8438, (12, 4) = .8461, (12, 5) = .8484, (12, 6) = .8508, (12, 7) = .8531, (12, 8) = .8554, (12, 9) = .8576, (12, 10) = .8599, (12, 11) = .8621, (13, 1) = `1.1`, (13, 2) = .8643, (13, 3) = .8664, (13, 4) = .8686, (13, 5) = .8707, (13, 6) = .8728, (13, 7) = .8749, (13, 8) = .8770, (13, 9) = .8790, (13, 10) = .8810, (13, 11) = .8830, (14, 1) = `1.2`, (14, 2) = .8849, (14, 3) = .8868, (14, 4) = .8887, (14, 5) = .8906, (14, 6) = .8925, (14, 7) = .8944, (14, 8) = .8962, (14, 9) = .8980, (14, 10) = .8997, (14, 11) = .9014, (15, 1) = `1.3`, (15, 2) = .9032, (15, 3) = .9049, (15, 4) = .9066, (15, 5) = .9082, (15, 6) = .9098, (15, 7) = .9114, (15, 8) = .9130, (15, 9) = .9146, (15, 10) = .9162, (15, 11) = .9177, (16, 1) = `1.4`, (16, 2) = .9192, (16, 3) = .9207, (16, 4) = .9222, (16, 5) = .9236, (16, 6) = .9250, (16, 7) = .9264, (16, 8) = .9278, (16, 9) = .9292, (16, 10) = .9304, (16, 11) = .9318, (17, 1) = `1.5`, (17, 2) = .9330, (17, 3) = .9346, (17, 4) = .9358, (17, 5) = .9370, (17, 6) = .9382, (17, 7) = .9394, (17, 8) = .9406, (17, 9) = .9418, (17, 10) = .9429, (17, 11) = .9440, (18, 1) = `1.6`, (18, 2) = .9452, (18, 3) = .9462, (18, 4) = .9473, (18, 5) = .9484, (18, 6) = .9494, (18, 7) = .9506, (18, 8) = .9516, (18, 9) = .9526, (18, 10) = .9536, (18, 11) = .9545, (19, 1) = `1.7`, (19, 2) = .9554, (19, 3) = .9564, (19, 4) = .9572, (19, 5) = .9582, (19, 6) = .9590, (19, 7) = .9599, (19, 8) = .9608, (19, 9) = .9616, (19, 10) = .9624, (19, 11) = .9633, (20, 1) = `1.8`, (20, 2) = .9641, (20, 3) = .9648, (20, 4) = .9656, (20, 5) = .9664, (20, 6) = .9671, (20, 7) = .9678, (20, 8) = .9686, (20, 9) = .9692, (20, 10) = .9699, (20, 11) = .9706, (21, 1) = `1.9`, (21, 2) = .9712, (21, 3) = .9719, (21, 4) = .9725, (21, 5) = .9732, (21, 6) = .9738, (21, 7) = .9744, (21, 8) = .9750, (21, 9) = .9756, (21, 10) = .9762, (21, 11) = .9767, (22, 1) = `2.0`, (22, 2) = .9772, (22, 3) = .9778, (22, 4) = .9783, (22, 5) = .9788, (22, 6) = .9793, (22, 7) = .9798, (22, 8) = .9802, (22, 9) = .9808, (22, 10) = .9812, (22, 11) = .9817, (23, 1) = `2.1`, (23, 2) = .9822, (23, 3) = .9826, (23, 4) = .9830, (23, 5) = .9834, (23, 6) = .9838, (23, 7) = .9842, (23, 8) = .9846, (23, 9) = .9850, (23, 10) = .9854, (23, 11) = .9857, (24, 1) = `2.2`, (24, 2) = .9860, (24, 3) = .9864, (24, 4) = .9868, (24, 5) = .9872, (24, 6) = .9874, (24, 7) = .9878, (24, 8) = .9881, (24, 9) = .9884, (24, 10) = .9887, (24, 11) = .9890, (25, 1) = `2.3`, (25, 2) = .9892, (25, 3) = .9896, (25, 4) = .9898, (25, 5) = .9901, (25, 6) = .9904, (25, 7) = .9906, (25, 8) = .9908, (25, 9) = .9911, (25, 10) = .9914, (25, 11) = .9916, (26, 1) = `2.4`, (26, 2) = .9918, (26, 3) = .9920, (26, 4) = .9922, (26, 5) = .9924, (26, 6) = .9926, (26, 7) = .9928, (26, 8) = .9930, (26, 9) = .9932, (26, 10) = .9934, (26, 11) = .9936, (27, 1) = `2.5`, (27, 2) = .9938, (27, 3) = .9940, (27, 4) = .9942, (27, 5) = .9943, (27, 6) = .9944, (27, 7) = .9946, (27, 8) = .9948, (27, 9) = .9949, (27, 10) = .9950, (27, 11) = .9952, (28, 1) = `2.6`, (28, 2) = .9954, (28, 3) = .9954, (28, 4) = .9956, (28, 5) = .9957, (28, 6) = .9958, (28, 7) = .9960, (28, 8) = .9961, (28, 9) = .9962, (28, 10) = .9963, (28, 11) = .9964, (29, 1) = `2.7`, (29, 2) = .9966, (29, 3) = .9966, (29, 4) = .9968, (29, 5) = .9968, (29, 6) = .9969, (29, 7) = .9970, (29, 8) = .9971, (29, 9) = .9972, (29, 10) = .9972, (29, 11) = .9974, (30, 1) = `2.8`, (30, 2) = .9974, (30, 3) = .9975, (30, 4) = .9976, (30, 5) = .9976, (30, 6) = .9978, (30, 7) = .9978, (30, 8) = .9979, (30, 9) = .9980, (30, 10) = .9980, (30, 11) = .9980, (31, 1) = `2.9`, (31, 2) = .9982, (31, 3) = .9982, (31, 4) = .9982, (31, 5) = .9983, (31, 6) = .9984, (31, 7) = .9984, (31, 8) = .9984, (31, 9) = .9985, (31, 10) = .9986, (31, 11) = .9986, (32, 1) = `3.0`, (32, 2) = .9986, (32, 3) = .9987, (32, 4) = .9988, (32, 5) = .9988, (32, 6) = .9988, (32, 7) = .9988, (32, 8) = .9989, (32, 9) = .9990, (32, 10) = .9990, (32, 11) = .9990, (33, 1) = `3.1`, (33, 2) = .9990, (33, 3) = .9990, (33, 4) = .9991, (33, 5) = .9991, (33, 6) = .9992, (33, 7) = .9992, (33, 8) = .9992, (33, 9) = .9992, (33, 10) = .9992, (33, 11) = .9993, (34, 1) = `3.2`, (34, 2) = .9993, (34, 3) = .9994, (34, 4) = .9994, (34, 5) = .9994, (34, 6) = .9994, (34, 7) = .9994, (34, 8) = .9994, (34, 9) = .9994, (34, 10) = .9995, (34, 11) = .9995, (35, 1) = `3.3`, (35, 2) = .9995, (35, 3) = .9996, (35, 4) = .9996, (35, 5) = .9996, (35, 6) = .9996, (35, 7) = .9996, (35, 8) = .9996, (35, 9) = .9996, (35, 10) = .9996, (35, 11) = .9996, (36, 1) = `3.4`, (36, 2) = .9996, (36, 3) = .9996, (36, 4) = .9997, (36, 5) = .9997, (36, 6) = .9997, (36, 7) = .9997, (36, 8) = .9998, (36, 9) = .9998, (36, 10) = .9998, (36, 11) = .9998, (37, 1) = `3.5`, (37, 2) = .9998, (37, 3) = .9998, (37, 4) = .9998, (37, 5) = .9998, (37, 6) = .9998, (37, 7) = .9998, (37, 8) = .9998, (37, 9) = .9998, (37, 10) = .9998, (37, 11) = .9998})

 

Download NormalTable.mw

Perhaps you will understand better if things are made more explicit rather than using the geometry package. MaplePrimes won't let me display this worksheet inline at the moment, but you can download it...

Download Ellipse.mw

...or just copy and paste this code into a Maple session:

Dist:= (P,Q)-> sqrt(add((P-Q)^~2)):  #Euclidean distance between points P and Q
Mid:= (P,Q)->  (P+Q)/2:              #Midpoint between P and Q

P:= <x,y>:                       #An arbitrary symbolic point on the ellipse
F:= [<0,-5>, <5, 0>]:  MA:= 12:  #Foci and major-axis length

(* An ellipse's defining property: The sum of the distances from any of its
points to its foci is constant. I'll call that constant C for the moment. 
We'll use that other piece of given information, the length of the major axis,
to figure out C in a moment. *)

Ell_eqn:= C = add(map(Dist, F, P));

# Perhaps you'll accept without further explanation that the line through 
# the foci (which is collinear with the major axis) is
MA_line:= y = x - 5;

(* The next step to getting C is finding numerically any point on the ellipse. 
Two such points are the points on that line that are at distance MA/2 from the
midpoint of the foci. We solve for them: *)

%solve({MA_line, Dist(P, Mid(F[])) = MA/2}, explicit);
sols:= value(%); 

# As suspected, there are 2 solutions. We only need 1, and I arbitrarily choose
# the first. To find C, we just use those x and y in the ellipse's equation:

eval(Ell_eqn, sols[1]);
eval(Ell_eqn, %):  #Put that in for C

# Subtract one side of the equation from the other to make an expression 
# implicitly equated to 0:

(lhs-rhs)(%);    
evala(Norm(%));      #Convert that to a polynomial
(primpart/sign)(%);  #Cancel common integer factors of the coefficients
#Final:
             119*x^2 - 50*x*y + 119*y^2 - 720*x + 720*y - 1584 

Your expression involves extreme underflows and overflows that can't be handled by the default hardware floats. So, the easy correction is

UseHardwareFloats:= false: 

An alternative is to simplify the expression to

f2:= exp(5002.646494 + 2499*ln(t) - 5000.*sqrt(t));

Then hardware floats can be used by plot.

My preferred syntax for situations like this is decisions[`if`(1 > T, 1, 2)].

I told you before that you need to change Gamma to GAMMA. You said that you did, but I still see Gamma.

Try entering it as A[b,c]. This makes it an indexed variable. The output will be subscripted like you want. An indexed variable is not quite the same thing as the atomic variable that you were trying to create, but it'll work if you do not assign values to Ab, or c.

The characters that you see are not apostrophes. Note that they lean to the left. They're called "back quotes" or "accents graves" or, in Maple, "name quotes". They let you make any string of characters, no matter how weird, into a variable.

However, you shouldn't be seeing those back quotes in your output. If I enter 

`A__b,c`;

then my output appears without quotes as Ab,c

You can set defaut options for all 3-D plots with the command

plots:-setoptions3d('axesfont'= ["TimesNewRoman", 24], 'labelfont'= ["TimesNewRoman", 24]);

These options can be overridden, if desired, on any individual plot command simply by including a different version of the option in the individual command.

You can use plots:-setoptions to do the same thing for 2-D plots.

These can be put into an initialization file which is automatically run whenever a new worksheet is loaded or a restart is executed.

One way:

(Int = rcurry(int, 'AllSolutions'))(1/x, x= a..2);

I have verified conclusively that the bondage number of your example graph is 7 by showing that a certain 7-subset of edges is a bondage set (that part is extremely easy), and using multithreaded processing with the Iterator package to verify exhaustively that none of the 439,381,916 edge subsets with less than 7 edges is a bondage set. With careful multithreading (using 8 threads on my computer), I reduced the average real time to verify whether an edge subset is a bondage set to about 17.3 microseconds (equivalent to about 3.4 million subsets checked per minute).

I'll put the main code and the worksheet separately because the main code is in a Code Edit Region within the worksheet.

MinBondageSet:= module()
option `Author: Carl Love <carl.j.love@gmail.com> 2023-Jun-22`;
local
    #Declaring module locals that are modified in multithreaded code as "thread_local"
    #causes the creation of a separate copy for each thread.
    A::thread_local #modified adjacency array after edge removal
;
export
    #All of this module's exports are essentially "static", but they're not declared
    #"static" because this module is not an "object"
    VL, n, V, A0, #VL = vertex labels, n= # of vertices, V={$n}, A0 = list of vertex neighborhoods
    edges, NE,
    DS, #minimum dominating sets of input graph, as a listlist

    #returns the set of minimum dominating sets of G as a listlist:
    MinDominatingSets:= module()
    local 
        N, s,
        Scans:= subs~(
            _s=~ [0, s, s[-1]],
            proc()
            local N0:= eval(N), Ns, v;
                N:= evaln(N); #garbage collection 
                (
                    for s, Ns in eval(N0) do
                    (
                        for v from _s+1 to n do
                            if (N[s,v]:= Ns union A0[v]) = V then [s,v] fi
                        od
                    )
                    od
                )
            end proc
        ),
        ModuleApply:= proc($)
        local Scan, R;
            N:= table([()= {}]);
            for Scan in Scans do if (R:= Scan()) <> () then return [R] fi od;
            [do R:= Scan() until R <> ()]
        end proc
    ;
    end module,

    GetEdges:= ()-> local k; seq['reduce'= `union`](`{}`~(k, select(`>`, A0[k], k)), k= 1..n-1),

    GetGraphData:= proc(G::Graph) #Assign exports specific to this graph:
        VL:= op(3,G);
        n:= nops(VL);                    
        V:= {$n};                             
        A0:= [seq](op(4,G) union~ `{}`~(V));  
        edges:= GetEdges();
        NE:= nops(edges);
        DS:= MinDominatingSets()
    end proc,

    #This proc essentially makes a local copy of the modified graph,
    #but does so in an efficient way:
    RemoveEdges:= proc(E::{set,list}(set), $)
    option threadsafe;
    local A1:= rtable(A0), e;
         for e in E do A1[e[1]] minus= {e[2]}; A1[e[2]] minus= {e[1]} od;
            A:= seq(A1); #This is why A is thread_local
            return
       end proc,

       #returns true iff no dominating set of the original graph is still dominating after
       #edge removal:
       CheckDS:= proc() option threadsafe; local d; andseq(`union`(A[d]) <> V, d= DS) end proc,
       
    #much slower than CheckDS, but potenially useful for some "greedy" algorithms: selects 
    #all of the original dominating sets that are still dominating after edge removal:
    ReduceDS:= ()-> select(d-> `union`(A[d]) = V, DS),

    ModuleApply:= module()
        local 
         k,        #size of edge subsets being checked
            Min, Max,    #min and max values of k to use  
            C,        #combinations Iterator for k-subsets
          st,        #time at start of an iteration
            found?,     #Flag set in one thread to make the others stop: Has a bondage set been found?

            TimeReport:= proc() #per-iteration userinfo timing report and estimate:
            local T:= time['real']() - st;
                if k = Min or T = 0 then return fi;
            userinfo(
                1, 'MinBondageSet', 'NoName',
                sprintf(
                    "Time to check %d-subsets of edges: %9.1f s; "
                    "expected time to check %d-subsets: %9.1f s.",
                    k, T, k+1, T*(NE-k)/(k+1)
                ) 
            ) 
        end proc
      ;
    export
            CheckSplit:= proc(rnk, num) #main multithreaded procedure:
            option threadsafe;
           local (h,g):= ModuleIterator(Object(C, 'rank'= rnk)), J:= g(), B;
                to num while h() do
                    RemoveEdges((B:= edges[[seq](J+~1)]));
                    if CheckDS() and not found? then found?:= true; return B fi
               until found? #can be set true by any thread
            end proc,

            ModuleApply:= proc(
               G::Graph,    
            { #keyword options:
                #Return after fully processing the input graph but 
                #before examining any edge subset:
                    setup_only::truefalse:= false,

                    #Skip the setup phase because the setup of G is already stored
                    #in the module:
                    no_setup::truefalse:= false,
                    
                    #sizes of edge subsets to check for being bondage sets:
                set_sizes::range({posint, identical()}):= .. 
                },
                $
            )
        uses It= Iterator, TT= Threads:-Task;
        local ne, R;        
            if not no_setup then GetGraphData(G) fi;
            if NE = 0 then return {} fi;
            if setup_only then return fi;

            Min:= lhs(set_sizes); if Min=() then Min:= 1 fi;
            Max:= rhs(set_sizes); if Max=() then Max:= NE fi;
            ne:= binomial(NE, Min);
            found?:= false;
            for k from Min to Max do
                    st:= time['real']();
                    C:= It:-RevolvingDoorCombination(NE, k);
                    R:= TT:-Start('passed', 'Tasks'= [CheckSplit, It:-SplitRanks(ne)[]]);
                    if R <> () then return R fi;
                    ne*= (NE-k)/(k+1); #update binomial(NE, k) -> binomial(NE, k+1) 
                    TimeReport()
            od
            end proc
    ;
    end module,

    #utility that lets the user convert vertex-label indices (default output) back
    #to the original vertex labels,
    LabelVertices:= e-> evalindets(e, integer[1..n], j-> VL[j])
;
end module
:


 

Minimum bondage sets of graphs[1]:

A multi-threaded use of the Iterator package

 

Author: Carl Love <carl.j.love@gmail.com> 2023-Jun-22

 

[1] We only consider here so-called simple graphs: no directed edges, no self-loops, no multiple edges. In other words, a simple graph's edge set is nothing more than a subset of the set of 2-subsets of its vertices. In the following worksheet, "graph" will always mean "simple graph" without further comment. Likewise, we only consider graphs with a finite number of vertices.

 

Definitions:

 

Of course, it's expected that the reader has some familiarity with graph theory; so, the first two definitions here are primarily to clarify my notation for the reader.

 

1. Graph, Vertices, Edges: A graph  is an ordered pair of sets G = (V, E), where V is any nonempty set (called the vertices), and E is any set of 2-subsets of V. E is called the edges.

 

Henceforth, let G = (V, E) be a graph.

 

2. Neighborhood: Given v 2V, the (closed} neighborhood  of v is the union of all edges containing v. The neighborhood of v contains v itself. If it's necessary to make that distinction (it isn't in this worksheet), it's called a closed neighborhood. For A3V, the neighborhood of A is the union of the neighborhoods of the elements of A.

 

3. Dominating set: A dominating set of G is a subset of V whose neighborhood is V.

 

4. Minimum dominating set: A minimum dominating set of G is a dominating set of the minimum size of all its dominating sets. (There is a closely related concept called a minimAL dominating set, which is not used in this worksheet.)

 

5. Domination number: The  (lower) domination number of G is the size of any of its minimum dominating sets. (A similar concept applied to minimAL dominating sets is called the upper domination number. We have no need of this here, so I'll just say domination number for the lower domination number.) The domination number of G is denoted by γ(G).

 

6. Bondage set: A bondage set (I prefer the term unbinding set) of G is a B 3 E such that the domination number of (V, E \ B) is greater than the domination number of G.

 

7. Minimum bondage set: A minimum bondage set of G is a bondage set of the minimum size of all its bondage sets.

 

8. Bondage number: The bondage  number of G is the size of any of its minimum bondage sets.

 

 

The following proposition is fundamental to the algorithm below, making it possible to function within a reasonable amount of time and memory:

 

Proposition: Let S be the set of all minimum dominating sets of G. A B 3E is a bondage set of G if and only if no member of S is a dominating set of (V, E \ B).

 

Proof: (0) If B is a bondage set, then γ((V, E \ B)) > γ(G). Thus every dominating set of (V, E \ B) has greater than γ(G) elements. Thus no dominating set of (V, E \ B) is in S.

 

(*) Removing an edge from G cannot decrease its domination number. Since S is all dominating sets of G of size γ(G), γ((V, E \ B)) >  γ(G). Thus B is a bondage set.

 

The bondage set produced as a result of the proposition is not necessarily minimum.

 

The reason that this can vastly improve the efficiency of finding a bondage set is that there are likely to be relatively few minimum dominating sets of G, and they'll always be the same regardless of the B currently being considered as a bondage set. In the main example below, there are 300 minimum bondage sets (of size 4) for a graph with |V| = 24. Checking whether any of these is a dominating set of (V, E \ B) is trivial. Indeed, we can stop as soon as any of the 300 is found to be dominating, thus verifying that B is not a bondage set.

 

Furthermore, that checking can be done by shared-memory parallel processing via Maple's Threads:-Task model using very little memory by using the Iterator package.

 

restart
:

MinBondageSet:= module()

#
# Example: A 7-regular graph with 24 vertices
#
g:= (GT:= GraphTheory):-Graph(
    (`union`@op@(`{}`~@op@`[]`)~)(
        [$24],
        [
            {2,3,4,5,7,9,11}, {3,5,6,7,12,14},  {4,7,8,9,16},  {5,9,10,11,17},
            {6,11,12,19},     {7,12,13,14,21},  {8,14,15},     {9,14,15,16,22},
            {10,16,17},       {11,17,18,19,23}, {12,18,19},    {13,19,20},
            {14,19,20,21,24}, {15,21},          {16,21,22,24}, {17,22,23},
            {18,22,23},       {19,20,23,24},    {20},          {21,23,24},
            {22,24},          {23,24},          {24},          {}
        ]
    )
);

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24], Array(1..24, {(1) = {2, 3, 4, 5, 7, 9, 11}, (2) = {1, 3, 5, 6, 7, 12, 14}, (3) = {1, 2, 4, 7, 8, 9, 16}, (4) = {1, 3, 5, 9, 10, 11, 17}, (5) = {1, 2, 4, 6, 11, 12, 19}, (6) = {2, 5, 7, 12, 13, 14, 21}, (7) = {1, 2, 3, 6, 8, 14, 15}, (8) = {3, 7, 9, 14, 15, 16, 22}, (9) = {1, 3, 4, 8, 10, 16, 17}, (10) = {4, 9, 11, 17, 18, 19, 23}, (11) = {1, 4, 5, 10, 12, 18, 19}, (12) = {2, 5, 6, 11, 13, 19, 20}, (13) = {6, 12, 14, 19, 20, 21, 24}, (14) = {2, 6, 7, 8, 13, 15, 21}, (15) = {7, 8, 14, 16, 21, 22, 24}, (16) = {3, 8, 9, 15, 17, 22, 23}, (17) = {4, 9, 10, 16, 18, 22, 23}, (18) = {10, 11, 17, 19, 20, 23, 24}, (19) = {5, 10, 11, 12, 13, 18, 20}, (20) = {12, 13, 18, 19, 21, 23, 24}, (21) = {6, 13, 14, 15, 20, 22, 24}, (22) = {8, 15, 16, 17, 21, 23, 24}, (23) = {10, 16, 17, 18, 20, 22, 24}, (24) = {13, 15, 18, 20, 21, 22, 23}}), `GRAPHLN/table/1`, 0)

MBS:= MinBondageSet:
infolevel[MBS]:= 1:

CodeTools:-Usage(MBS(g, setup_only));

memory used=13.97MiB, alloc change=37.00MiB, cpu time=109.00ms, real time=77.00ms, gc time=62.50ms

# Just out of curiosity, display and count the dominating sets:
#
MBS:-DS;

[[3, 6, 10, 21], [3, 6, 10, 24], [3, 11, 17, 21], [6, 9, 10, 21], [6, 9, 10, 24], [11, 14, 16, 18], [11, 14, 16, 20], [11, 14, 16, 21], [11, 14, 16, 23], [11, 14, 16, 24], [4, 6, 16, 18], [4, 6, 16, 20], [1, 16, 19, 21], [7, 10, 15, 19], [1, 13, 19, 22], [1, 8, 10, 13], [2, 14, 17, 18], [4, 7, 17, 20], [2, 10, 22, 24], [6, 8, 11, 18], [6, 8, 11, 23], [1, 6, 16, 18], [3, 6, 15, 18], [6, 9, 15, 18], [5, 6, 8, 18], [5, 6, 8, 23], [1, 12, 14, 23], [2, 4, 20, 22], [1, 11, 16, 21], [1, 14, 17, 20], [1, 13, 14, 17], [1, 13, 14, 23], [3, 12, 17, 21], [1, 7, 20, 23], [2, 12, 15, 17], [4, 14, 17, 20], [5, 8, 20, 23], [2, 9, 18, 21], [2, 9, 18, 24], [2, 4, 15, 20], [4, 6, 15, 18], [4, 6, 15, 20], [7, 13, 17, 19], [3, 14, 19, 22], [3, 14, 19, 23], [2, 10, 16, 20], [2, 10, 16, 21], [2, 10, 16, 24], [4, 6, 8, 18], [4, 6, 8, 20], [3, 11, 18, 21], [1, 6, 15, 18], [3, 6, 16, 18], [6, 9, 16, 18], [5, 7, 13, 17], [3, 13, 19, 22], [1, 6, 8, 18], [9, 10, 12, 15], [7, 12, 15, 17], [6, 7, 17, 18], [4, 13, 14, 17], [4, 13, 14, 23], [2, 9, 12, 24], [4, 8, 12, 20], [4, 8, 12, 24], [6, 11, 16, 18], [6, 11, 16, 20], [6, 11, 16, 21], [6, 11, 16, 23], [6, 11, 16, 24], [6, 7, 10, 23], [5, 8, 21, 23], [2, 9, 19, 22], [2, 9, 19, 24], [3, 17, 19, 21], [9, 12, 15, 17], [9, 12, 15, 18], [9, 12, 15, 20], [9, 12, 15, 23], [9, 12, 15, 24], [3, 13, 16, 19], [3, 7, 19, 22], [1, 13, 17, 22], [4, 7, 15, 20], [1, 5, 14, 23], [6, 8, 9, 18], [5, 8, 9, 20], [5, 8, 9, 24], [2, 10, 15, 19], [2, 10, 15, 20], [2, 10, 15, 21], [2, 10, 15, 24], [3, 6, 8, 18], [1, 10, 13, 15], [1, 10, 13, 16], [1, 10, 13, 22], [4, 6, 18, 22], [3, 19, 21, 22], [3, 19, 21, 23], [1, 7, 17, 20], [2, 8, 10, 13], [2, 8, 10, 20], [2, 8, 10, 21], [2, 8, 10, 24], [4, 6, 19, 22], [5, 9, 15, 20], [5, 9, 15, 24], [2, 12, 17, 22], [4, 14, 15, 20], [5, 8, 18, 20], [5, 8, 18, 21], [5, 8, 18, 24], [4, 5, 14, 23], [2, 9, 11, 24], [11, 13, 14, 16], [5, 7, 17, 20], [5, 7, 17, 21], [5, 7, 17, 24], [8, 9, 12, 20], [8, 9, 12, 24], [3, 16, 19, 21], [1, 13, 16, 17], [1, 13, 16, 18], [1, 13, 16, 19], [1, 13, 16, 23], [1, 8, 13, 17], [1, 8, 13, 18], [1, 8, 13, 23], [4, 7, 16, 20], [1, 2, 19, 22], [3, 5, 21, 23], [3, 6, 18, 21], [3, 6, 18, 22], [3, 6, 18, 24], [6, 9, 18, 21], [6, 9, 18, 22], [6, 9, 18, 24], [2, 11, 13, 16], [9, 12, 14, 23], [9, 12, 14, 24], [7, 10, 12, 15], [7, 10, 12, 22], [1, 13, 18, 22], [1, 10, 12, 15], [2, 10, 14, 23], [5, 6, 16, 18], [5, 6, 16, 23], [5, 8, 19, 22], [4, 5, 15, 20], [4, 5, 15, 24], [2, 5, 9, 24], [7, 15, 17, 19], [3, 12, 18, 21], [3, 18, 19, 21], [4, 6, 20, 22], [7, 11, 13, 16], [7, 11, 13, 17], [1, 7, 19, 22], [5, 9, 14, 23], [5, 9, 14, 24], [5, 14, 16, 18], [5, 14, 16, 23], [4, 14, 16, 20], [7, 12, 13, 17], [1, 13, 15, 17], [1, 13, 15, 18], [1, 13, 15, 23], [2, 9, 10, 21], [2, 9, 10, 24], [3, 5, 10, 21], [4, 8, 14, 20], [4, 7, 8, 20], [1, 11, 21, 22], [7, 9, 12, 24], [3, 12, 21, 23], [2, 4, 19, 22], [1, 9, 20, 21], [4, 12, 15, 17], [4, 12, 15, 18], [4, 12, 15, 20], [4, 12, 15, 23], [4, 12, 15, 24], [2, 17, 19, 22], [2, 10, 13, 15], [2, 10, 13, 16], [2, 10, 13, 22], [3, 11, 13, 16], [3, 11, 13, 22], [5, 6, 9, 24], [1, 12, 15, 17], [1, 12, 15, 18], [1, 12, 15, 23], [2, 3, 18, 21], [2, 3, 18, 24], [4, 7, 13, 17], [4, 7, 13, 23], [3, 5, 18, 21], [6, 9, 11, 24], [7, 17, 19, 20], [7, 17, 19, 21], [7, 17, 19, 22], [7, 17, 19, 24], [6, 11, 13, 16], [8, 11, 12, 22], [2, 15, 17, 19], [11, 12, 15, 16], [1, 11, 13, 16], [1, 11, 13, 22], [5, 8, 17, 20], [5, 8, 17, 21], [5, 8, 17, 24], [4, 10, 12, 15], [3, 11, 21, 22], [3, 11, 21, 23], [5, 8, 10, 13], [5, 8, 10, 20], [5, 8, 10, 21], [5, 8, 10, 24], [4, 12, 14, 23], [2, 10, 12, 15], [2, 10, 12, 22], [3, 11, 14, 23], [2, 3, 19, 22], [2, 10, 19, 22], [1, 6, 19, 22], [6, 9, 12, 24], [5, 7, 9, 24], [3, 6, 19, 22], [6, 9, 19, 22], [6, 9, 19, 24], [5, 8, 23, 24], [2, 4, 8, 20], [4, 14, 19, 22], [4, 14, 19, 23], [5, 8, 14, 18], [5, 8, 14, 23], [7, 9, 19, 22], [7, 9, 19, 24], [3, 12, 14, 23], [7, 11, 17, 20], [7, 11, 17, 21], [7, 11, 17, 24], [1, 11, 14, 23], [1, 9, 13, 24], [1, 14, 19, 22], [1, 14, 19, 23], [4, 7, 20, 22], [4, 7, 20, 23], [5, 15, 16, 19], [3, 10, 11, 21], [4, 11, 14, 23], [2, 10, 20, 22], [1, 6, 18, 22], [2, 11, 16, 20], [2, 11, 16, 21], [2, 11, 16, 24], [5, 8, 13, 17], [5, 8, 13, 18], [5, 8, 13, 23], [9, 11, 14, 23], [9, 11, 14, 24], [1, 7, 13, 17], [1, 7, 13, 23], [2, 4, 16, 20], [3, 12, 15, 17], [3, 12, 15, 18], [3, 12, 15, 23], [7, 11, 16, 20], [7, 11, 16, 21], [7, 11, 16, 24], [1, 19, 21, 22], [7, 9, 11, 24], [4, 14, 20, 22], [4, 14, 20, 23], [1, 14, 20, 23], [7, 12, 17, 20], [7, 12, 17, 21], [7, 12, 17, 22], [7, 12, 17, 24], [4, 5, 8, 20], [4, 5, 8, 24], [3, 5, 14, 23], [8, 11, 14, 18], [8, 11, 14, 23], [2, 10, 21, 22], [3, 5, 17, 21], [3, 10, 19, 21], [4, 7, 19, 22], [9, 14, 19, 22], [9, 14, 19, 23], [9, 14, 19, 24], [3, 10, 12, 15], [3, 10, 12, 21], [1, 13, 22, 23], [7, 10, 19, 22], [3, 4, 20, 21], [2, 3, 10, 21], [2, 3, 10, 24], [3, 11, 16, 21], [3, 4, 13, 24]]

nops(%);

300

#
# Remove a specific subset of 7 edges (all edges adjacent to vertex 1), and prove that the
# domination number is <= 7:
#
MBS:-RemoveEdges(`{}`~(1, {2,3,4,5,7,9,11}));
MBS:-CheckDS();

true

#
# That means that none of g's original 300 minimum dominating sets is still dominating;
# thus the domination number must have increased; thus the bondage number is <= 7.
#
# Prove that the bondage number is > 5 by exhaustive multi-threaded search:
#
CodeTools:-Usage(MBS(g, no_setup, set_sizes= ..5));

Time to check 2-subsets of edges:       0.6 s; expected time to check 3-subsets:      15.9 s.

Time to check 3-subsets of edges:       1.6 s; expected time to check 4-subsets:      32.8 s.

Time to check 4-subsets of edges:      29.2 s; expected time to check 5-subsets:     467.9 s.

Time to check 5-subsets of edges:     537.7 s; expected time to check 6-subsets:    7079.2 s.

memory used=182.78GiB, alloc change=267.31MiB, cpu time=70.33m, real time=9.50m, gc time=5.44m

# time per edge subset checked:
(0.6 + 1.6 + 29.2 + 537.7)/add(binomial(84,k), k= 1..5);

0.1729767728e-4

60/%;

3468673.801

# So, it's using about 16 microseconds per edge subset checked.
# I'm using an Intel Core i7-7700HQ with 4 cores @ 2.8 GHz. There are 2 hyperthreads
# per core, so a total of 8 threads in the parallel process.

 

I also ran MinBondageSet on the 6-subsets of edges, finding no bondage sets. This takes about 2 hours on my computer. Memory usage is trivial. This confirms that the bondage number is 7.

 

Download BondageNumber.mw

Suggestions:

The circles for r = 1/3 and r = 2/3 serve no didactic purpose, and thus I think that they're detrimental to the pedagogy.

You need rays for theta = Pi/4, 3*Pi/4, etc.

The vertical lines should not extend beyond the circle. If they go outside the circle, it's easy to mistake them as stray marks. Their color should be more visible.

Your series has no free variables. The concept of radius of convergence doesn't make sense without a free variable such that the convergence of the series depends on that free variable being within a certain "radius" of some point. The concept of power series requires a free variable which is raised to "powers".  

First 10 11 12 13 14 15 16 Last Page 12 of 382