Anh chị ui. Có ai biết cách trình bày 2 đồ thị đẳng cấu như thế nào không ạ?

Ví dụ như câu 5a đề Test ý ạ. Em không biết trình bày như thế nào nữa.

Cảm ơn anh chị nhiều!

Ban QT: Xem bài giảng của thầy P đã trình bày quá rõ rồi. Bây giờ không ai có thời gian để gõ bài cơ bản lên đâu. Hoặc Google hoặc chờ sau 14/8 mới có thời gian gõ cho bạn. Về nguyên tắc bạn cần chỉ định từng đỉnh của đồ thị thứ nhât tương ứng với từng đỉnh của đồ thị thứ 2 về số bậc, số cạnh, số chu trình con... bằng nhau và ngược lại (song ánh)...

Ngồi buồn tự nhiên hứng lên đưa một bài đồ thị đẳng cấu lên cho mọi người làm. Mình nghĩ nếu làm được bài này thì kiến thức cơ bản về đẳng cấu cũng tạm ổn.

Đề bài như sau: Kiểm tra xem hai đồ thị sau có đẳng cấu hay không?
G1={(u1,u2),(u1,u4),(u1,u5),(u2,u5),(u2,u4),(u2,u3),(u3,u4),(u4,u5)}
G2= {(v1,v3),(v1,v4),(v1,v5),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(v4,v5)}

Ban QT: Lưu ý thành viên không nên dùng dấu ngoặc nhọn { } vì các diễn đàn họ PunBB thường nhầm với mã điều khiển, nên nó hay tự động xóa mất dữ liệu khi Post. Nên dùng dấu ngoặc đơn. Nếu vẫn thích dùng dấu ngoặc nhọn, nên để dấu ngoặc nhọn trong thẻ code là thẻ có hình [You must be registered and logged in to see this image.]

Vẽ hình ra, hai thằng này có một hình chóp, sau đó thêm một hình tam giác nữa. Chắc là đẳng cấu nhỉ.

Bài này có u2, u4 tương ứng với v3, v5; u1, u5 tương ứng với v1, v4 còn u3 và v2 thì tương ứng với nhau, hai đồ thị này đẳng cấu. Ai có ý kiến khác post lên nha.

Bước 1. Vẽ 2 đồ thị ra ta có:
Đồ thị gồm:
[You must be registered and logged in to see this image.] Vẽ thế này để ta nhìn cho dễ xem nó có đẳng cấu không? [You must be registered and logged in to see this image.]

Bước 2: Chứng minh đẳng cấu:
1) Các đỉnh tương ứng đề nghị Khách viếng thăm liệt kê giúp, ví dụ U3 tương ứng với V2...
Từ đó chỉ ra:
- Các đỉnh có cùng bậc 2 tương ứng là U3, V2
- Các đỉnh có cùng bậc 4 tương ứng là U2, U4 với V3, V5
- Các đỉnh có cùng bậc 3 tương ứng là U1, U5 với V1, V4
- Các chu trình con qua đỉnh bậc 2 và 4 tương ứng là U3 → U2 → U4 tương ứng với V2 → V3 → V5
...
Vậy 2 đồ thị là đẳng cấu. (Việc liệt ke bằng cách kẻ bảng các điều gợi ý trên đề nghị Khách viếng thăm tự thực hiện)

Bài dạng này có thể vẽ hình ra cho dễ nhìn cũng được (không bắt buộc). Các bước chứng minh nó đẳng cấu:
1. Chỉ ra hàm f tương ứng 1-1 giữa các đỉnh của 2 đồ thị
2. Kiểm tra f có bảo tồn các cạnh hay không bằng cách kiểm tra ma trận kề của 2 đồ thị. chú ý vị trí các đỉnh phải tương ứng qua hàm f.
Các đ/c có thể đọc ví dụ 7.21 tr 141 trong cuốn "tài liệu ôn thi cao học Toán rời rạc" của TS Nguyễn Thiện Luận để xem chi tiết.

Ban QT: Vì tài liệu ai cũng có, ai cũng biết, nên không cần gõ lên tránh mất thì giờ, đề nghị mọi người xem lại.

Quan trọng nhất là phải cho ra được ma trận kề, thế là OK

Để chứng minh 2 đồ thị là đẳng cấu theo em các anh chị nên làm như sau, lấy luôn ví dụ của anh Tống và gợi ý của anh Admin nha. Phần tô màu là phần anh chị phải chép vào bài viết, phần chữ thường thì anh chị đừng có chép vào nha, đó là em lý luận để anh chị hiểu các bước phải làm thôi.

Bước 1. Các anh chị lập một cái bảng và sắp xếp bậc của đồ thị tăng dần trước. Vậy ta cần ghi vào bài làm câu sau: Sắp xếp các đỉnh của từng đồ thị theo chỉ số bậc tăng dần là:

Bậc đỉnh	Các đỉnh bậc 2	Các đỉnh bậc 3	Các đỉnh bậc 4	Ghi chú
Đồ thị G1	U3	U1, U5	U2, U4
Đồ thị G2	V2	V1, V4	V3, V5

Bước 2: Định nghĩa hàm f

Nếu vẽ được thì anh chị hãy vẽ ra 2 cái hình như anh Admin vẽ nha. Cố gắng vẽ giống như anh ý là tốt nhất để có thể có cơ sở khẳng định luôn là đẳng cấu.

Lý luận như sau vào bài viết: Căn cứ vào bảng trên ta có thể định nghĩa hàm f tạm thời như sau, nếu đúng thì dùng luôn, nếu sai sẽ định nghĩa lại.

Cứ nói như vậy, vì mình đã chọn tất nhiên là đúng rồi, đây là bước giả sử coi như chưa biết mà (vì thực chất là đã biết tỏng rồi, nên cứ nói cho nó đúng trình tự).

Ta có:

f(U₃) = V₂

Vì đỉnh U₃ nối với 2 đỉnh bậc 4 là U₂ và U₄, và đỉnh V₂ cũng nối với 2 đỉnh bậc 4 là V₃ và V₅ nên ta chọn tiếp:

f(U₂) = V₃
f(U₄) = V₅

Căn cứ vào tính chất liền kề của các đỉnh tương ứng vừa chọn, ta thấy đỉnh U₂ nối với 2 đỉnh U₁ và U₅ như nhau, đồng thời đỉnh V₃ cũng là nối với 2 đỉnh V₁ và V₄ như nhau, nên ta chọn tiếp hàm f như sau:

f(U₁) = V₁
f(U₅) = V₄

Như vậy ta đã lập được phép tương ứng 1 -1 đối với 2 đồ thị G₁ và G₂.

Đến đây anh chị hãy mỉm cười 1 cái cho nó có duyên và làm cho mình xả bớt stress. Sau đó anh chị chuyển sang bước kế nha.

Bước 3: Lập ma trận kề đối chứng song ánh.

Anh chị kẻ 2 bảng để đối chứng nha, kẻ như sau. Bảng 1, như bài này có 5 đỉnh, thì anh chị kẻ bảng 6 x 6 nha, thừa 1 hàng là hàng đầu tiên, anh chị gõ đỉnh là ảnh của đỉnh tương ứng, tức là cái gì là kết quả của f đó. Ví dụ như trên có V₂ là kết quả của f(U₃) vì f(U₃) = V₂. Anh chị đừng ghi lộn xộn mà hãy ghi theo thứ tự đã sắp xếp các đỉnh ở bảng bước 1 vừa làm. Em làm như thế này nha (việc này để cố tình tạo ra đối xứng qua đường chéo chính):

Ta có A_G1 =

	V2	V1	V4	V3	V5
U3	0	0	0	1	1
U1	0	0	1	1	1
U5	0	1	0	1	1
U2	1	1	1	0	1
U4	1	1	1	1	0

Viết một bảng AG₂ sao cho giống hệt với AG₁ với ảnh tương ứng của G₁ qua G₂ và ngược lại.

Ta có A_G2 =

	U3	U1	U5	U2	U4
V2	0	0	0	1	1
V1	0	0	1	1	1
V4	0	1	0	1	1
V3	1	1	1	0	1
V5	1	1	1	1	0

Đến đây anh chị lại thở phào 1 cái nữa nhé, cho nó vui. Rồi ghi vào bài làm như sau:

Vì AG₁ = AG₂ ta suy ra f bảo tồn các cạnh. Vậy ta kết luận f là một phép đẳng cấu hay G₁ và G₂ đẳng cấu.

Hai đồ thị này đẳng cấu. Phương pháp mọi người chỉ ra đúng hướng rồi đấy. Quan trọng nhất là xây dựng được hàm f.

Cho em xin cuốn tài liệu này với ạ.