Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: bài tập lý thuyết đồ thị

  1. #1
    Ngày gia nhập
    12 2007
    Bài viết
    4

    Wink bài tập lý thuyết đồ thị

    chà mình có máy bài toán bên phần lý thuyết đồ thị đang bị bí mong các bạn chỉ giáo cho
    1) Một lớp có 60 sv,trong đó mỗi sv có ít nhất 30 email của các sv còn lại.
    Chứng minh rằng bất cứ 2 sv trong lờp đều liên lạc với nhau
    2) Trong cộc liên hoan mọi người bắt tay nhau.Hãy chứng minh tổng số lượt người bắt tay là một số chẵn.Giả sử không ai tự bắt tay mình
    Mong các bạn giúp đỡ minh nha.Chỉ cần gợi ý cho mình thui.
    Cảm ơn nhiều

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Câu 2 vô cùng đơn giản.
    Giả sử A bắt tay B thì B cũng bắt tay A, như vậy nếu tồn tại 1 cái bắt tay t1 giữa A và B thì luôn tồn tại 1 bắt tay t1* giữa B và A.

    Như thế chưa chặt chẽ để chứng minh số bắt tay là số chẵn . Bác nào tiếp đi.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Câu 1 :

    Giả sử tồn tại 1 người A không liên lạc được với 1 người B nào đó.

    Ta gọi tập {B1, B2, ..., B30} là những người mà liên lạc được với người B.

    Như vậy, người A không liên lạc được với {B1, B2, ... B30} (vì nếu liên lạc được thì đã liên lạc được với B)

    Ta có tiếp, người A không liên lạc được với {B, B1, B2, ... B30}. Như vậy người A không liên lạc được với 31 người.

    Giả sử người A có khả năng liên lạc được với tất cả những người còn lại, cũng chỉ được 60 - 31 - 1 = 28. Trái với giả thiết.

    Điều còn lại dàng cho chủ topic.

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Cả 2 bài chẳng có liên quan 1 chút gì đến 2 từ "Đồ thị", thầy cô nào bảo bạn 2 bài này thuộc lý thuyết đồ thị vậy ?
    - Dùng xác xuất, tổ hợp, tập hợp CM kiểu nào cũng xong.
    - Dùng phản chứng cũng được.
    ps : tự suy nghĩ, cả 2 bài đều quá cơ bản.

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    có liên quan đến đồ thị đó chứ. Tớ viết lại đề bài nhé.

    Bài 1:

    Cho một đồ thị có hướng, gồm 60 đỉnh. Mỗi đỉnh có thể đi đến chính xác 30 đỉnh khác.
    Chứng minh rằng đồ thị là liên thông toàn phần.

    Bài 2:
    Chứng minh rằng khi một đồ thị vô hướng sang đồ thị có hướng thì số cạnh của đồ thị có hướng là chẵn.

  6. #6
    Ngày gia nhập
    09 2010
    Bài viết
    1

    Mặc định bài tập lý thuyết đồ thị

    Quá hay!!! không nghề từ Toán học dịch sang lý thuyết đồ thị lại hay vậy.
    Chắc mình đổi ý chuyển nghành thuj.Theo lập trình thui.
    Bạn còn bà nào hay kjeu này nữa hok?
    pót lên anh em tranh luận chơi

Các đề tài tương tự

  1. Thuyết Trình Ext Js for asp.net
    Gửi bởi bigs1993 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 07-12-2013, 11:06 PM
  2. lý thuyết đồ thị!
    Gửi bởi phamtuan04081989 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 17-05-2010, 03:22 PM
  3. lý thuyết tô màu cho đồ thị
    Gửi bởi #include# trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2008, 04:11 PM
  4. Lý thuyết đồ thị với C++
    Gửi bởi CuongNH trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 15-04-2008, 09:39 AM
  5. [Phụ lục C] - Dành cho tra cứu lý thuyết C
    Gửi bởi Kevin Hoang trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 22-08-2006, 11:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn