Nickles

30 Reputation

2 Badges

10 years, 45 days

MaplePrimes Activity


These are questions asked by Nickles

This is pretty similar to my last question. but I found this maple code on a website that is suppose to find a vertex coloring of a graph G. The output is is supposed to be a list for example like [3, table([y = 1, k = 2, c = 2, m = 3, h = 1, x = 1] where the first part (in this case 3) is the number of colors and 1,2,3 in the second part are the colors to which each vertex is assigned.  However, no matter what graph I run this on I get everything equal to 1. such as [1, table([y = 1, k = 1, c = 1, m = 1, h = 1, x = 1])]. Why is this happening?  
color:=proc(G)
  local i, j, C, U, V, total_used;
  V:=Vertices(G); total_used:=1;
  C[V[1]]:=1;
  for i from 2 to nops(V) do
    C[V[i]]:=0;
  end do;
  for i from 2 to nops(V) do
    U:={};
      for j from 1 to nops(neighbors(V[i], G)) do
      U:=U union C[neighbors(V[i], G)[j]];
       end do;
    j:=1;
    while member(j, U) do
      j:=j+1;
     end do;
    C[V[i]]:=j;
    if j>total_used then
      total_used:=j;
    end if;
   end do;
  [total_used, eval(C)];
end:

So the pseudocode I'm trying to translate into maple is for the greedy vertex coloring algorithm.

The pseudo code is:

Initialize:
1. for i = 1 to n do
2. f[i] := 0 (: no color assigned yet to vertex i :)
3. end(for)
Main loop:
4. for i = 1 to n do
5. let f[i] be the smallest positive integer
which is not in the set {f(j) : j ∈ adj[i]}
6. end(for)
7 return f

 

The closest I've gotten though is:

greedy := proc (G)

local i, j, n, k, L::list;

description "Take simple graph G and return a coloring of the vertices with at most Delta(G)+1 colors";

n := nops(Vertices(G));
L := [seq(x, i = 1 .. n)];
L := subsop(1 = c(1), L);
j := 1;
for i from 2 to n do
L[Vertices(G)[i]] := c(0)
end do;

for i from 2 to n do
   for k to i do
        if member(Vertices(G)[i], Neighbors(G, Vertices(G)[k])) then j := j+1
       end if; 
   end do;
L[Vertices(G)[i]] := c(j)
end do;
return L;
end proc;

Basically my procedure is returning more than delta+1 colors for most graphs, how can I edit it to fix this? I'm guessing the problem is somewhere in my nested loops. Also, I cannot use commands like greedycolor or isvertexcolorable. Thanks.

 

So I'm trying to make a procedure to tell is a sequence is graphical or not.
seqgraph:= proc (L::list)

local k::integer, i::integer, n::integer, a::integer, S;

n := numelems(L);

S := convert(L, `+`);

a := 0;

if type(S, odd) then print("not graphical")

else for k to n do

if add(L[i], i = 1 .. k) <= k(k-1)+add(min(k, L[i]), i = k+1 .. n) then a := a+1

else a := a+2

end if;

end do;

end if;
if n = a then print(graphical)

else print("not graphical")

end if;

end proc;

 

 I'm trying to say that if that equality (which is part of the erdos gallai theorem) holds for that value of k then we'll add one to a value (a). Thus, if a=n at the end then the ineuqality was true for each k and thus it would it should print "graphical" but every list I test it one prints 'not graphical'. Where is my mistake? I get an error saying it can't execute add?

So for the part of the erdos gallai theorem that says:


\sum^{k}_{i=1}d_i\leq k(k-1)+ \sum^n_{i=k+1} \min(d_i,k)

 

how could I translate this into maple? I'm assuming I'll need to use nested for...dos

If I have a list, how can I write a program to see is that list is graphical? So far I have

graphicalseq := proc (L::list)

local i::integer, N;

N := convert(L, `+`);


if type(N, odd) then print("Sequence is not graphical")


else if numelems(L)-1 < L[1] then print("Sequence is not graphical")
end if;


end if;

end proc;

I know I still have to keep going to determine whether the sequence is graphical, but I'm not sure how.

 I was thinking of trying to somehow use Havel-Hakimi's theorem, but again I'm not sure how. Any hints would be appreciated.  I can't use the is Graph Sequence function

1 2 Page 1 of 2