to finding the chromatic set

Question

Kajal Agrawal 2023-6-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1977434-to-finding-the-chromatic-set

评论： Kajal Agrawal 2023-6-6

we want to chromatic number.

step1- creat a square matrix and first assign 0 in a set.

step 2- From the above matrix we select 1st vertex and assigned red color. Cut the row and column.

step 3- In the first cut row vertex with zero entry is 4 (vertex), so assign the same red color to it, and cut the corresponding row and column of vertex 4.

Step 4- Now in both the cut row no zero is left so we proceed to the next vertex 2 from the non-cut row assign the color green and cut the row and column 3 with the same color following the same steps. Finally, vertex 5 and 6 get colored with the third color. As shown in Figure 1 of Section 3.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Kajal Agrawal 2023-6-4

移动：John D'Errico 2023-6-4

I want an algorithm. First, We create any square matrix and do some operations on it. select 1st vertex and assigned any color then Cut the row and column. In the first cut row vertex with zero (0) entry is in 4 (vertex), so assign the same color to it. Same step follow for the next vertex.next vertex is 2nd and assign the other color( green) and zeros is in 3rd vertex assign the same color (green) to it. At the end we have number of colors.

John D'Errico 2023-6-4

You already HAVE the algorithm, as confusingly stated as it is. But as a pure question about an algorithm, this does not even belong on a MATLAB forum.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Tushar 2023-6-4

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1977434-to-finding-the-chromatic-set#answer_1250139

在 MATLAB Online 中打开

Hi Kajal,

I think you are trying to run the above algorithm on a matrix and trying to calculate the minimum number of different colors required to do so. If this is the case , in my opinion the following algorithm very closely does the same. But in this implementation, note two things:

Cutting of any row or column is implemented by replacing the entries in that row or column by -1.
Secondly, se calculating the answer from the length of the array "colors" which can contain duplicate values. SO in order to calculate unique values ,we can utilize the function "unique" and then count the number of elements by "numel".
Also, I have initialized the matrix randomly. You can use the matrix in place of it for which you want to calculate the chromatic number.

function [matrix, num_colors] = simulate_procedure(n)
    % Step 1: Initialize colors set
    colors = [];
    % Step 2: Create matrix and initialize with random values
    matrix = randi([0, 1], n, n);
    % Step 3: Assign color to the first vertex (vertex 1)
    colors = [colors, 1];
    color = 'red';  % Assign any color you like
    % Step 4: Cut row and column of the first vertex
    matrix(:, 1) = -1;
    matrix(1, :) = -1;
    % Step 5: Process remaining vertices
    for vertex = 2:n
        % Check if zero entry exists in the cut row of the current vertex
        if any(matrix(vertex, :) == 0)
            % Assign the same color as the previous vertex
            colors = [colors, vertex];
            if strcmp(color, 'red')
                color = 'green';
            else
                color = 'red';
            end
            % Cut row and column of the current vertex
            matrix(:, vertex) = -1;
            matrix(vertex, :) = -1;
        end
    end
    % Step 6: Number of colors used (after removing duplicates)
    num_colors = numel(unique(colors));
end
% Usage example
n = 6;
[matrix, num_colors] = simulate_procedure(n);
disp('Matrix:');
disp(matrix);
disp(['Number of colors: ', num2str(num_colors)]);