Log in to Mathigon

Google
Create New Account

Reset Password     

Chia sẻ

Thay đổi ngôn ngữ

EnglishVietnamese

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

Bảng chú giải

Select one of the keywords on the left…

Đồ thị và Mạng lướiTiệc tùng và hẹn hò

Tiết lộ tất cả các bước

Hãy tưởng tượng bạn được mời tham dự một buổi tiệc sang trọng. Tính thêm cả bạn và chủ tiệc thì có tổng cộng ${hnd} người tham dự.

Cuối buổi tiệc khi mọi người chuẩn bị ra về, mọi người bắt tay nhau. Vậy có tất cả bao nhiêu cái bắt tay?

Nếu minh họa những cái bắt tay bằng một đồ thị thì mỗi người tham gia là một đỉnhmột cạnh, và mỗi cái bắt tay là một cạnhmột đỉnh.

Vậy giờ ta có thể dếm dễ dàng số lượng cạnh của đồ thị, với ${hnd} người, có tất cả ${hnd*(hnd-1)/2} cái bắt tay.

Thay vì đếm tất cả các cạnh trong một đồ thị lớn, ta cũng có thể tìm một công thức đơn giản để tính ra kết quả với bất kỳ số lượng nào của người tham dự tiệc.

Mỗi người trong số ${n} người đến tham dự tiệc bắt tay với ${n-1} người khác. Vậy là có ${n} × ${n-1} = ${n×(n-1)} cái bắt tay tất cả. Cho số n người, số cái bắt tay sẽ là n × (n – 1)n × (n + 1)n2.

${handshakeTable(n)}

Tuy nhiên thật ra kết quả này là không đúng: bởi chúng ta đã đếm mỗi cái bắt tay hai lầnmột lầnba lần, vì hai người tham gia chỉ bắt tay một lần với nhau.

Ví dụ, hai cái bắt tay đầu tiên ở hàng trên cùng thực ra là một. Số cái bắt tay đúng cho ${n} người tham dự là ${n} × ${n-1}2 = ${n*(n-1)/2}.

Đồ thị minh họa những cái bắt tay rất đặc biệt vì các đỉnh đều kết nối với các đỉnh còn lại. Đồ thị với đặc tính này được gọi là đồ thị hoàn chỉnh. Đồ thị hoàn chỉnh có 4 đỉnh được viết tắt là K4, đồ thị hoàn chỉnh với 5 đỉnh được ký hiệu là K5, v...v...

Chúng ta vừa thấy rằng đồ thị có n đỉnh, ký hiệu Kn, có tất cả n×n12 cạnh.

Vào một ngày đẹp trời khác, bạn được mời đến tham dự một buổi hẹn hò tốc hành (speed dating) cho ${m} bạn nam và ${f} bạn nữ. Ban tổ chức sắp đặt những cái bàn nhỏ để mỗi bạn nam có thể có 5 phút với mỗi bạn nữ. Vậy tổng cộng có bao nhiêu "cuộc gặp gỡ" đã diễn ra?

Trong trường hợp này, đồ thì tương ứng có hai tập đỉnh khác nhau. Mỗi đỉnh được kết nối với tất cả các đỉnh của nhóm đối diệncủa chính nhóm đó, nhưng không kết nối với các đỉnh của chính nhóm đónhóm đối diện. Đồ thị với đặc tính này được gọi là đồ thị hai phía.

Đồ thị hai phía với hai tập đỉnh xy thường được ký hiệu là Kx,y. Đồ thị này có x × yx + y2_x_ – y cạnh, nghĩa là trong ví dụ trên có tất cả ${m} × ${f} = ${m×f} cuộc gặp gỡ.