Discussion :

[lamyaee]

bonjour ,svp jai un projet qui s'intitule d'un thème qui a pour objectif l'implantation de l'algorithme de coloriage des sommets d'un graphe sur matlab. svp jai besoin d'aide si quelqu'un a une idée.
merci d'avance

[Jean Dumoncel]

Bonjour,

ou bloques-tu précisément?

[jcanivet]

l'utilisation de la dérivée est un bon début (fonction diff), dérivée première et seconde sont utiles.

[lamyaee]

merci bien
voila le code que jai utilisé (disponible ici) mais l'erreur que j'obtiens est la suivante:
Error in ==> dsatur at 14
for i=1:n

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function [coloring] = dsatur(V,E)
 
%n = size(V,1);
%coloring = zeros(n,1);
%available_colors = 1;
 
% Start with the node that has the maximum degree.
% Color the current node with the lowest available color.
% Select the next node by selecting the node with the maximum degree of saturation.
% This means that you have to select the node that has the most number of unique neighboring colors.
% In case of a tie, use the node with the largest degree.
% Goto step 2. until all nodes are colored.
 
% Degrees
for i=1:n
    v = i;
    Degrees(i,1) = size([E(find(E(:,1)==v),2); E(find(E(:,2)==v),1)],1);
end
 
% Degrees of saturation
Degrees_of_saturation = zeros(n,1);
 
% Coloring
for i=1:n
    if i == 1
        [value index] = max(Degrees);
        v = index(1);
        coloring(v) = 1;
        assigned_color_v = 1;
    else
        Uncolored = find(coloring==0);
        index_temp = find(Degrees_of_saturation(Uncolored)==max(Degrees_of_saturation(Uncolored)));
        index = Uncolored(index_temp);
        if(size(index,1)>1)
            [value1 index1] = max(Degrees(index));
            v = index(index1);
        else
            v = index;
        end
 
        % Assign first available color to v
        neighbors = [E(find(E(:,1)==v),2); E(find(E(:,2)==v),1)];
        for j=1:available_colors
            if size(find(coloring(neighbors)==j),1)==0
                coloring(v) = j;
                assigned_color_v = j;
                break;
            end
        end
        if coloring(v) == 0
            available_colors = available_colors + 1;
            coloring(v) = available_colors;
            assigned_color_v = available_colors;
        end
    end
 
    % Update Degrees of saturation
    neighbors_v = [E(find(E(:,1)==v),2); E(find(E(:,2)==v),1)];
    for j=1:size(neighbors_v,1)
       u = neighbors_v(j);
       neighbors_u = [E(find(E(:,1)==u),2); E(find(E(:,2)==u),1)];
       if size(find(coloring(neighbors_u)==assigned_color_v),1) == 1
           Degrees_of_saturation(u,1) = Degrees_of_saturation(u,1) + 1;
       end
    end
 
end

[Jean Dumoncel]

Enlève les commentaires sur les lignes 3 à 5, elles sont utiles pour le reste du code.

[lamyaee]

oui j'ai essayé cela mé il donne un autre message d'erreur présenté comme suit:
Error in ==> dsatur at 2
n = size(V,1);