bươc tiếp theo la gì vay anh
Hướng giải quyết bài toán tô màu đồ thị
Dùng danh sách kề giảm độ phức tạp bài toán đi 
và tô màu cũng dễ.
2 Likes
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ề.
1 Like
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
1 Like
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.
1 Like
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);
}
1 Like
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:
@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
vang ạ.em cảm ơn anh nha
1 Like
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] ;
}
}
1 Like
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)
Có thể là không giải được nếu đồ thị liên thông 3 đỉnh
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
Google đổi security link cũ ko vào được., gửi email hoài. vào link dưới nhé
2 Likes
mình nhớ hồi xưa làm là : chọn đỉnh có bậc lớn nhất tô trước, các đỉnh kề nó -1 bậc, đỉnh vừa tô set bậc = 0 , lặp lại cho tới khi chỉ còn các đỉnh bậc 0 và tô màu nhỏ nhất có thể tô
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?