حل مساله رنگ آمیزی گراف با الگوریتم پس گرد — به زبان ساده

انواع گوناگونی از مسائل رنگ‌آمیزی گراف وجود دارد که مساله رنگ کردن راس‌های گراف، یکی از محبوب‌ترین و متداول‌ترین آن‌ها به شمار می‌آید. در این مساله، یک گراف غیر مستقیم و عدد m داده شده است. هدف رنگ کردن راس‌های گراف به صورتی است که هیچ دو راس مجاوری، دارای رنگ مشابه نباشند. m تعداد رنگ‌های داده شده است. باید توجه داشت که در اینجا منظور از رنگ‌آمیزی، تخصیص رنگ به راس‌های گراف است. برای حل مساله رنگ آمیزی گراف، الگوریتم‌های گوناگونی ارائه شده که «الگوریتم پس گرد» (Backtracking) و «حریصانه» (Greedy) از این جمله هستند. در این مطلب، هدف حل مساله رنگ آمیزی گراف با الگوریتم پس گرد است.

تعریف مساله

تعداد m رنگ و یک گراف داده شده است. هدف رنگ کردن راس‌های این گراف به صورتی است که هیچ دو راس مجاوری دارای یک رنگ مشابه نباشند. ورودی و خروجی مساله، به طور دقیق به شرح زیر هستند.

فیلم آموزش نظریه گراف و کاربردها در فرادرس

کلیک کنید

ورودی:

1. یک آرایه دو بعدی، یعنی گراف [graph[V][V که در آن، V تعداد یال‌ها در گراف را مشخص می‌کند و [graph[V][V نمایش ماتریس همسایگی گراف است. مقدار [graph[i][j در صورتی که یک یال مستقیم از i به j وجود داشته باشد برابر با یک، و در غیر این صورت، مقدار [graph[i][j برابر با ۰ است.
2. عدد صحیح m، تعداد کل رنگ‌هایی است که می‌توان از آن‌ها استفاده کرد.

خروجی:

آرایه [color[V که باید حاوی اعدادی از ۱ تا m باشد. [color[i باید رنگ تخصیص یافته به i‌اُمین راس را نشان دهد. همچنین، در صورتی که نمی‌توان گراف را با m رنگ طبق شرط موجود رنگ‌آمیزی کرد، کد باید مقدار False را بازگرداند. در ادامه، تصویری از یک گراف داده شده که با m=3 رنگ (سفید، سبز، قرمز) رنگ‌آمیزی شده است.

الگوریتم ساده

الگوریتم ساده ارائه شده در زیر، همه پیکربندی‌های ممکن برای رنگ‌آمیزی گراف را که شروط داده شده در آن‌ها رعایت می‌شود، در خروجی چاپ می‌کند.

while there are untried conflagrations
{
generate the next configuration
if no adjacent vertices are colored with same color
{
print this configuration;
}
}

به تعداد V^m  پیکربندی مختلف از رنگ‌ها وجود دارد.

حل مساله رنگ آمیزی گراف با الگوریتم پس گرد

ایده اساسی آن است که رنگ‌ها یکی یکی به راس‌های مختلف اختصاص پیدا کنند. این کار با شروع از راس صفر (۰) آغاز می‌شود. پیش از تخصیص رنگ، امکان‌پذیری تخصیص رنگ بر اساس شرط داده شده بررسی می‌شود.

فیلم آموزش طراحی الگوریتم در فرادرس

کلیک کنید

این کار، با در نظر گرفتن رنگ‌هایی که در حال حاضر به راس‌های همسایه تخصیص پیدا کرده‌اند، صورت می‌پذیرد. اگر الگوریتم تشخیص دهد که تخصیص یک رنگ مشخص در شرط داده شده صدق می‌کند، تخصیص رنگ به عنوان بخشی از راهکار انجام می‌شود. اگر رنگی برای یک راس مشخص پیدا نشود که در شرط مذکور صدق کند، پس‌گرد انجام و پیغام خطای False صادر می‌شود.

کد راه حل مساله رنگ آمیزی گراف در ++C/C

#include<stdio.h> 
#include<stdbool.h> 
  
// Number of vertices in the graph 
#define V 4 
  
void printSolution(int color[]); 
  
/* A utility function to check if the current color assignment 
is safe for vertex v i.e. checks whether the edge exists or not 
(i.e, graph[v][i]==1). If exist then checks whether the color to  
be filled in the new vertex(c is sent in the parameter) is already 
used by its adjacent vertices(i-->adj vertices) or not (i.e, color[i]==c) */
bool isSafe (int v, bool graph[V][V], int color[], int c) 
{ 
    for (int i = 0; i < V; i++) 
        if (graph[v][i] && c == color[i]) 
            return false; 
    return true; 
} 
  
/* A recursive utility function to solve m coloring problem */
bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) 
{ 
    /* base case: If all vertices are assigned a color then 
       return true */
    if (v == V) 
        return true; 
  
    /* Consider this vertex v and try different colors */
    for (int c = 1; c <= m; c++) 
    { 
        /* Check if assignment of color c to v is fine*/
        if (isSafe(v, graph, color, c)) 
        { 
           color[v] = c; 
  
           /* recur to assign colors to rest of the vertices */
           if (graphColoringUtil (graph, m, color, v+1) == true) 
             return true; 
  
            /* If assigning color c doesn't lead to a solution 
               then remove it */
           color[v] = 0; 
        } 
    } 
  
    /* If no color can be assigned to this vertex then return false */
    return false; 
} 
  
/* This function solves the m Coloring problem using Backtracking. 
  It mainly uses graphColoringUtil() to solve the problem. It returns 
  false if the m colors cannot be assigned, otherwise return true and 
  prints assignments of colors to all vertices. Please note that there 
  may be more than one solutions, this function prints one of the 
  feasible solutions.*/
bool graphColoring(bool graph[V][V], int m) 
{ 
    // Initialize all color values as 0. This initialization is needed 
    // correct functioning of isSafe() 
    int color[V]; 
    for (int i = 0; i < V; i++) 
       color[i] = 0; 
  
    // Call graphColoringUtil() for vertex 0 
    if (graphColoringUtil(graph, m, color, 0) == false) 
    { 
      printf("Solution does not exist"); 
      return false; 
    } 
  
    // Print the solution 
    printSolution(color); 
    return true; 
} 
  
/* A utility function to print solution */
void printSolution(int color[]) 
{ 
    printf("Solution Exists:"
            " Following are the assigned colors \n"); 
    for (int i = 0; i < V; i++) 
      printf(" %d ", color[i]); 
    printf("\n"); 
} 
  
// driver program to test above function 
int main() 
{ 
    /* Create following graph and test whether it is 3 colorable 
      (3)---(2) 
       |   / | 
       |  /  | 
       | /   | 
      (0)---(1) 
    */
    bool graph[V][V] = {{0, 1, 1, 1}, 
        {1, 0, 1, 0}, 
        {1, 1, 0, 1}, 
        {1, 0, 1, 0}, 
    }; 
    int m = 3; // Number of colors 
    graphColoring (graph, m); 
    return 0; 
} 

کد راه حل مساله رنگ آمیزی گراف در جاوا

/* Java program for solution of M Coloring problem 
   using backtracking */
public class mColoringProblem { 
    final int V = 4; 
    int color[]; 
  
    /* A utility function to check if the current 
       color assignment is safe for vertex v */
    boolean isSafe(int v, int graph[][], int color[], 
                   int c) 
    { 
        for (int i = 0; i < V; i++) 
            if (graph[v][i] == 1 && c == color[i]) 
                return false; 
        return true; 
    } 
  
    /* A recursive utility function to solve m 
       coloring  problem */
    boolean graphColoringUtil(int graph[][], int m, 
                              int color[], int v) 
    { 
        /* base case: If all vertices are assigned 
           a color then return true */
        if (v == V) 
            return true; 
  
        /* Consider this vertex v and try different 
           colors */
        for (int c = 1; c <= m; c++) 
        { 
            /* Check if assignment of color c to v 
               is fine*/
            if (isSafe(v, graph, color, c)) 
            { 
                color[v] = c; 
  
                /* recur to assign colors to rest 
                   of the vertices */
                if (graphColoringUtil(graph, m, 
                                      color, v + 1)) 
                    return true; 
  
                /* If assigning color c doesn't lead 
                   to a solution then remove it */
                color[v] = 0; 
            } 
        } 
  
        /* If no color can be assigned to this vertex 
           then return false */
        return false; 
    } 
  
    /* This function solves the m Coloring problem using 
       Backtracking. It mainly uses graphColoringUtil() 
       to solve the problem. It returns false if the m 
       colors cannot be assigned, otherwise return true 
       and  prints assignments of colors to all vertices. 
       Please note that there  may be more than one 
       solutions, this function prints one of the 
       feasible solutions.*/
    boolean graphColoring(int graph[][], int m) 
    { 
        // Initialize all color values as 0. This 
        // initialization is needed correct functioning 
        // of isSafe() 
        color = new int[V]; 
        for (int i = 0; i < V; i++) 
            color[i] = 0; 
  
        // Call graphColoringUtil() for vertex 0 
        if (!graphColoringUtil(graph, m, color, 0)) 
        { 
            System.out.println("Solution does not exist"); 
            return false; 
        } 
  
        // Print the solution 
        printSolution(color); 
        return true; 
    } 
  
    /* A utility function to print solution */
    void printSolution(int color[]) 
    { 
        System.out.println("Solution Exists: Following" + 
                           " are the assigned colors"); 
        for (int i = 0; i < V; i++) 
            System.out.print(" " + color[i] + " "); 
        System.out.println(); 
    } 
  
    // driver program to test above function 
    public static void main(String args[]) 
    { 
        mColoringProblem Coloring = new mColoringProblem(); 
        /* Create following graph and test whether it is 
           3 colorable 
          (3)---(2) 
           |   / | 
           |  /  | 
           | /   | 
          (0)---(1) 
        */
        int graph[][] = {{0, 1, 1, 1}, 
            {1, 0, 1, 0}, 
            {1, 1, 0, 1}, 
            {1, 0, 1, 0}, 
        }; 
        int m = 3; // Number of colors 
        Coloring.graphColoring(graph, m); 
    } 
} 
// This code is contributed by Abhishek Shankhadhar 

کد راه حل مساله رنگ آمیزی گراف در پایتون

# Python program for solution of M Coloring  
# problem using backtracking 
  
class Graph(): 
  
    def __init__(self, vertices): 
        self.V = vertices 
        self.graph = [[0 for column in range(vertices)]\ 
                              for row in range(vertices)] 
  
    # A utility function to check if the current color assignment 
    # is safe for vertex v 
    def isSafe(self, v, colour, c): 
        for i in range(self.V): 
            if self.graph[v][i] == 1 and colour[i] == c: 
                return False
        return True
      
    # A recursive utility function to solve m 
    # coloring  problem 
    def graphColourUtil(self, m, colour, v): 
        if v == self.V: 
            return True
  
        for c in range(1, m+1): 
            if self.isSafe(v, colour, c) == True: 
                colour[v] = c 
                if self.graphColourUtil(m, colour, v+1) == True: 
                    return True
                colour[v] = 0
  
    def graphColouring(self, m): 
        colour = [0] * self.V 
        if self.graphColourUtil(m, colour, 0) == False: 
            return False
  
        # Print the solution 
        print "Solution exist and Following are the assigned colours:"
        for c in colour: 
            print c, 
        return True
  
# Driver Code 
g  = Graph(4) 
g.graph = [[0,1,1,1], [1,0,1,0], [1,1,0,1], [1,0,1,0]] 
m=3
g.graphColouring(m) 
  
# This code is contributed by Divyanshu Mehta 

خروجی

Solution Exists: Following are the assigned colors
1 2 3 2

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس

^^