mới lượm được cái đề của mấy trường khác nên quăng lên đây cho anh em tham khảo,nhân tiện ai biết cách trình bày thì làm mẫu 1 bài (bài đơn giản thôi cũng được) để anh em tham khảo cách trình bày
Câu 1(2điểm) cho một đồ thị vô hướng bởi ma trận kề sau:

0 1 0 0 0 1
1 0 1 1 0 0
0 1 0 0 1 1
0 1 0 0 1 0
0 0 1 1 0 1
1 0 1 0 1 0

a. hãy cho biết đồ thị đã cho có chu trình euler không? Nếu không thì có đường đi euler không?vì sao?nếu có thì chỉ ra nó?
b. Đồ thị đó có là đồ thị phẳng không,vì sao?
Câu 2(2điểm)
Hai đồ thị G1 và G2 sau có đẳng cấu hay không?vì sao?G1 cho dưới dạng ma trận kề M,đồ thị G2 cho dưới dạng danh sách cạnh kề L:
0 1 1 0 1 0
1 0 0 1 1 0
M= 1 0 0 1 1 1
0 1 1 0 0 1
1 1 1 0 0 0
0 0 1 1 0 0


L= { (4,2),(4,3),(3,2),(4,6),(1,3),(1,5),(1,6),(5,3),(5 ,6)}

Câu 3 (2 điểm)
Cần bao nhiêu đợt thi để không có sinh viên nòa phải thi 2 môn cùng 1
thời đợt, biết rằng có 8 môn thi đươc đánh số từ 1 đến 8 và có các cặp
môn thi có chung sv thi là: (1,5) (1,4) (1,6) (1,7) (2,4) (2,5) (2,
(3,5) (3, (4,6) (6,7) (7..


Bài 4(4 điểm)
Cho 1 đồ
thị có trọng số gồm 8 đỉnh (các đỉnh được đánh số từ 1,3,….., dưới
dạng danh sách cạnh kề như nhau(mỗi cạnh cho dưới dạng (i,j,c) trong đó
I,j là chỉ số đỉnh, c là trọng số): (1,2,1) (1,3,7) (1,6,3) (2,3,9)
(2,4,17) (2,5,7) (3,4, (3,8, (4,8.4) (5,6,2) (5,7,4) (5,8, (7,8,1)
a. Hãy tìm cây khung nhỏ nhất của đồ thị (nêu rõ cách tìm)
b. Hãy tìm đường đi ngắn nhất từ đỉnh 2 đến đỉnh 4 bằng phương pháp dijsktra hoặc bằng phương pháp Floyd?

ặc! thật không phải là đơn giản nhỉ! hjhj!

sax có ai giải được cái này hem?????? nhìn vô chẳng hỉu gì chài

bubupro.gdty đã viết:

sax có ai giải được cái này hem?????? nhìn vô chẳng hỉu gì chài

câu 1:
a/không có chu trình cũng như đường đi euler vì có quá 2 đỉnh bậc lẽ (cả thảy 4 đỉnh)
b/không phải đồ thị phẳng do có cạnh cắt nhau ở ngoài đỉnh

[You must be registered and logged in to see this image.]

hình câu 1 không biết đúng k nữa

[You must be registered and logged in to see this image.]

giải thử câu 2

k	d[a], truoc[a]	d[b], truoc[b]	d[c], truoc[c]	d[d], truoc[d]	d[e], truoc[e]	d[f], truoc[f]
	0,b	0,b	A,b	A,b	A,b	A,b
1	0,b	0,b	17,a	10,a	A,b	1,a

câu 2 tui nghĩ làm zậy tại tới đây thì đường tới f đã tối ưu nên kết thúc thuật toán

câu 1: áp dụng thuật toán Fleury

Trích dẫn :

Xuất phát từ 1 ta có 2 lựa chọn:qua
đỉnh 2 hoặc 7


TH1: qua đỉnh 2


Tại
đỉnh 2 ta có 3 lựa chọn là qua đỉnh 3 hoặc 4,hoặc 7


TH1.1:qua đỉnh 3


Tại
3 ta chỉ có duy nhất 1 lựa chọn là qua 4(do đó dù (3,4) có là cầu cũng phải
qua)


Tại
4 ta có 2 lựa chọn là qua đỉnh 5 hoặc 8


TH1.1.1:qua đỉnh
5


Tại
5 chỉ có 1 lựa chọn là qua 6,sau đó tiếp tụ qua 7,tại 7 có 3 lựa chọn là 8 hoặc
1 hoặc 2 nhưng (7,1) và (7, là cầu nên
sẽ chọn đi qua đỉnh 2->4->8->7->1


Chu
trỉnh Euler là {1,2,3,4,5,6,7,2,4,8,7,1}


TH1.1.2:qua đỉnh
8


Tại
8 chỉ có 1 lựa chọn là qua đỉnh 7 có 3 lựa chọn là: 6 hoặc 1 hoặc 2 nhưng (7,1)
là cầu nên chọn 6 hoặc 2


Nếu
chọn 6 thì có chu trình euler là: {1,2,3,4,,8,7,6,5,4,2,7,1}


Nếu
chọn 2 thì có chu trình euler là: {1,2,3,4,8,7,2,4,5,6,7,1}


TH1.2:qua đỉnh 4


Tại đỉnh 4 có 3 lựa
chọn là: 3,5,8


TH1.2.1:qua đỉnh 3


Tại
3 có 1 lựa chọn là qua đỉnh 2->7 tại 7 có 2 lựa chọn là: 6 hoặc 8


Nếu
chọn 6 thì có chu trình euler là:{1,2,4,3,2,7,6,5,4,8,7,1}


Nếu
chọn 8 thì có chu trình euler là:{1,2,4,3,2,7,8,4,5,6,7,1}


TH1.2.2:
qua đỉnh 5


Tại 5 có 1 lựa chọn là qua 6 và 7,tại
7 có 2 lựa chọn là qua 8 hoặc 2


Nếu chọn 2 thì có chu trình euler
là:{1,2,4,5,6,7,2,3,4,8,7,1}


Nếu chọn 8 thì có chu trình euler
là:{1,2,4,5,6,7,8,4,3,2,7,1}


TH1.2.3:qua
đỉnh 8


Tại 8 có 1 lựa chọn là qua 7,tại 7
có 2 lựa chọn là:2 hoặc 6


Nếu chọn 2 thì có chu trình euler
là:{1,2,4,8,7,2,3,4,5,6,7,1}


Nếu chọn 6 thì có chu trình euler
là:{1,2,4,8,7,6,5,4,3,2,7,1}
.......

chỉ làm vài cái minh họa thui,chứ làm hết chắc tới sáng. [You must be registered and logged in to see this image.]