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

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)n².

${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×n−12 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?

Đồ thị hai phía với hai tập đỉnh x và y 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ỡ.