Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    chungct


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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)...

    2 Bài tập đồ thị đẳng cấu!!! on Wed Aug 10, 2011 5:22 pm

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    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.]


    ================

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    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ỉ.


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

    4 [Hướng dẫn] on Wed Aug 10, 2011 8:35 pm

    sinhmd


    Quản trị viên
    Quản trị viên
    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. ~)


    ================

    http://climategis.com/forum/

    Admin


    Quản trị viên
    Quản trị viên
    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)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    hienha


    Chuyên viên
    Chuyên viê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.


    ================

    mrP


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


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

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Để 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 đỉnhCác đỉnh bậc 2Các đỉnh bậc 3Các đỉnh bậc 4Ghi chú
    Đồ thị G1U3U1, U5U2, U4

    Đồ thị G2V2V1, V4V3, 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(U3) = V2

    Vì đỉnh U3 nối với 2 đỉnh bậc 4 là U2 và U4, và đỉnh V2 cũng nối với 2 đỉnh bậc 4 là V3
    và V5 nên ta chọn tiếp:

    f(U2) = V3
    f(U4) = V5

    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 U2 nối với 2 đỉnh U1 và U5 như nhau, đồng thời đỉnh V3 cũng là nối với 2 đỉnh V1 và V4 như nhau, nên ta chọn tiếp hàm f như sau:

    f(U1) = V1
    f(U5) = V4

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


    Đế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ó V2 là kết quả của f(U3) vì f(U3) = V2. 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ó AG1 =



    V2V1V4V3V5
    U300011
    U100111
    U501011
    U211101
    U411110
    Viết một bảng AG2 sao cho giống hệt với AG1 với ảnh tương ứng của G1 qua G2 và ngược lại.

    Ta có AG2 =

    U3U1U5U2U4
    V200011
    V100111
    V401011
    V311101
    V511110
    Đế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ì AG1 = AG2 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 G1 và G2 đẳng cấu.


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    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.


    ================

    lethanhtrung


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Cho em xin cuốn tài liệu này với ạ.

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Create a forum on Forumotion | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs