Hướng giải quyết bài toán tô màu đồ thị

Xài mảng 6x6 là đúng rồi đó bạn, mình phải lưu lại ma trận kể chứ

bươc tiếp theo la gì vay anh

Dùng danh sách kề giảm độ phức tạp bài toán đi và tô màu cũng dễ.

Dùng danh sách kề giảm độ phức tạp bài toán đi và tô màu cũng dễ.

Mình nghĩ vì số đỉnh nhỏ nên dùng ma trận kề thì truy xuất nhanh hơn danh sách kề.

Bạn thử code theo thuật toán phía dưới, nếu không được thì mình share code sau nhé

Tô màu đồ thị: tô màu đồ thị sao cho hai đỉnh kề nhau có màu khác nhau và sử dụng số màu ít nhất như có thể.
Thuật toán
Sắp thứ tự danh sách các đỉnh theo bậc giảm dần.
Gọi m là số màu cần sử dụng, ban đầu m=0;
Trong khi còn đỉnh chưa tô{
m=m+1;
Gán màu m cho đỉnh chưa được tô màu đầu tiên trong danh sách và lần lượt cho các đỉnh chưa tô màu trong danh sách và không kề với các đỉnh có màu m.
}
Chú ý: thuật toán thường cho kết quả với số màu tô ít nhất nhưng không phải luôn là như vậy.

Ví dụ:
a) Cho đơn đồ thị vô hướng 7 đỉnh, dạng ma trận trọng số như sau:

HD:
Stt:4>5>6>1>2>3>7
màu 1: 4, 1, 7
màu 2: 5,2,3
màu 3: 6

em vẫn không hiểu lam.a cho e xin code luôn duoc khong ạ

có ngĩa bau giờ minh sap xep bac giam dan theo cot hay theo hàng deu duoc hả anh

Bậc của một đỉnh chính là số đỉnh kề với nó. Đầu tiên, em cần tính bậc của tất cả các đỉnh và lưu vào mảng, sau đó sắp xếp mảng này giảm dần.

a xem cho em phan hàm tìm bâc của các đỉnh dúng chưa ạ

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

int bac(int m,int n,int a[7][7])
{
    int i,j,bac;
    for(i=1;i<=n;i++)
    {
        bac=0;
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==1)
            {
                bac=bac+1;
            }
        }
        return bac;
    }
}


int main()
{
    int maudinh[6],a[7][7];
    int n,i,j,m,tg;
    {
        printf("nhap vao so hang m");
        scanf("%d",&m);
        printf("nhap vao so cot n");
        scanf("%d",&n);
    }
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            printf("a[%d][%d]",i,j);
            scanf("%d",&tg);
            a[i][j]=tg;
        }
    }
    printf("mang da nhap vao \n");
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)printf("%2d",a[i][j]);
        printf("\n");
    }
    int t;
    t=bac(m,n,a[7][7]);
    printf("t=%3d",t);
}

http://codepad.org/x3ti2LSr

Anh bổ sung code lên diễn đàn luôn cho @Tri_H_i_D_ng

Cách post code là thêm dấu ` như hình dưới.

```c
void main()
{

}
``` 

Link hướng dẫn cách post code lên diễn đàn cụ thể ở đây:

Làm sao để có thể hiển thị syntax highlighting bằng markdown? Các bạn phải đánh dấu ``` như ví dụ dưới đây Chú ý, dấu ``` được tạo ra bởi nút nằm bên trái số 1 trên bàn phím, nút này sẽ là ~ khi bấm giữ Shift Ví dụ cho C Nội dung: ``` void main() { } ``` Và đừng quên ``` ở cuối Kết quả void main() { } Ví dụ cho Pascal Nội dung: ``` Program HelloWorld; Begin WriteLn('Hello world!') {no ";" is required after the last statement of a block - adding one adds a "null stateme…

@Tri_H_i_D_ng em đặt câu hỏi và thảo luận trong topic này rất tốt, tiếc là anh học cái này lâu rồi, giờ không còn nhớ để trả lời giúp em được. Hi vọng em sẽ tìm được câu trả lời cho mình.

Cảm ơn em đã đọc và làm theo hướng dẫn đặt câu hỏi của anh

em cảm ơn anh ạ.a xem cho em cái phần tìm bậc của đỉnh đồ thị với.em mà không viết hàm thì em tim đươc bâc của đỉnh,còn khi dùng hàm tìm đỉnh thì không ra.mong a giúp em

Rất muôn giúp nhưng anh quên hết rồi. À, anh đã share cho @Gio xem. và @Gio có trả lời ở đây:

facebook.com

Đạt Lê Trần

Mọi người vào giúp 1 tay :)

vang ạ.em cảm ơn anh nha

Bậc của một đỉnh chính là số đỉnh kề của đỉnh đó.
Vì ma trận kề chỉ lưu giá trị 0 và 1 nên ta có thể tính để bậc của một đỉnh là tổng trên hàng tương ứng. Ví dụ, bậc của đỉnh 1 tổng các giá trị trên hàng thứ 1, tức là bac[1] = a[1][1] + a[1][2]+ a[1][3] + …+ a[1][n]

int n ; // n là số đỉnh
int bac[10000]  // mảng lưu trữ bậc. Ví dụ, a[i] = m thì bậc của đỉnh đỉnh là m 
int a[100][100] // ma trận kề
for(int i = 1 ; i <= n ; i++ ) { 
	for(int j = 1; j<=n;j++  ) { 
		bac[i] += a[i][j] ; 
	}
}

em làm được đến bước đó oy anh,bây giờ mình làm gì tiếp hả anh

Bạn thử xem cái này có phải cái bạn cần ? (sorry nếu không phải)

GeeksforGeeks – 1 May 12

m Coloring Problem | Backtracking-5 - GeeksforGeeks

Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent… Read More »

Có thể là không giải được nếu đồ thị liên thông 3 đỉnh

sử dụng số màu ít nhất như có thể.

why not? ít nhất có một lời giải mà

Bai này ngày trước anh có giải
Em xem đây nhé:
https://drive.google.com/file/d/0B5d8cee5X6WmY3h6djUwNU43cDg/view?usp=sharing