Mình đang học môn lý thuyết đồ thị, có một bài tập này mình vẫn chưa nghĩ ra cách giải, nhờ mọi người giúp đỡ. Cảm ơn
Bài toán như nhau:
Cho tập X gồm n phần tử, xây dựng đồ thị vô hướng G với các đỉnh là các tập con của X. Hai đỉnh kề nhau nếu hai tập con tương ứng không giao nhau. Hỏi đồ thị này có bao nhiêu cạnh?
a. $(3^{n} + 1) / 2$
b.$ 3^{n} / 2$
c. $(3^{n} - 1) / 2$
Như vậy đồ thị G có thể là không đơn. Tại đỉnh tập rỗng là có khuyên:
- Số đỉnh kề đỉnh tập rỗng là : đỉnh tập rỗng và $2^{n}-1 $ đỉnh còn lại. Nên bậc của đỉnh tập rỗng là: $2^{n}+1=C^0_n2^n+1 $
- Số đỉnh kề với đỉnh có 1 phần tử là: $2^{n-1} $. Do đó tồng bậc của các đỉnh có 1 phần tử là $C^1_n2^{n-1} $
...
- Số đỉnh kề với đỉnh có k phần tử là: $2^{n-k} $. Do đó tồng bậc của các đỉnh có k phần tử là $C^k_n2^{n-k} $
=> Tổng bậc của các đỉnh trong G là $C^0_n2^n+1+ C^1_n2^{n-1}+ ...+C^k_n2^{n-1}+...+C^n_n2^{n-n}=\sum\limits_{k = 0}^n {C_n^k 2^{n - k} } + 1 =3^n+1$
Gọi m là số cạnh của G. Ta có 2m = tổng bậc các đỉnh. Suy ra $m = \dfrac{{3^n + 1}}{2}$
