Log in to Mathigon

Google
Create New Account

Reset Password     

Share

Change Language

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.

Glossary

Select one of the keywords on the left…

Các bản dịch vẫn đang được phát triển và có thể không đầy đủ.

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

Reveal All Steps

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à , và mỗi cái bắt tay là .

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à .

${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 , 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 , nhưng không kết nối với các đỉnh của . Đồ 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ó cạnh, nghĩa là trong ví dụ trên có tất cả ${m} × ${f} = ${m×f} cuộc gặp gỡ.