Tìm tất cả maximal clique có kích thước "n"
Bây giờ bạn đã khám phá tam giác (và tam giác mở), hãy chuyển sang khái niệm maximal clique. Maximal clique là những clique không thể mở rộng thêm bằng cách bổ sung một cạnh kề, và là một thuộc tính hữu ích của đồ thị khi tìm cộng đồng. NetworkX cung cấp một hàm cho phép bạn xác định các nút tham gia vào mỗi maximal clique trong một đồ thị: nx.find_cliques(G). Hãy thử nghiệm hàm này với T trong IPython Shell, rồi quay lại trả lời bài tập.
Bài tập này là một phần của khóa học
Nhập môn Phân tích Mạng bằng Python
Hướng dẫn bài tập
- Viết một hàm
maximal_cliques()có hai tham số -Gvàsize- để tìm tất cả các maximal clique có kích thướcn.- Trong vòng lặp
for, duyệt qua tất cả các clique trongGbằng hàmnx.find_cliques(). - Nếu clique hiện tại có kích thước bằng
size, hãy thêm nó vào danh sáchmcs.
- Trong vòng lặp
- Dùng một câu lệnh assert và hàm
maximal_cliques()của bạn để kiểm tra rằng có33maximal clique có kích thước3trong đồ thịT.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
# Define maximal_cliques()
def ____:
"""
Finds all maximal cliques in graph `G` that are of size `size`.
"""
mcs = []
for clique in ____:
if ____ == ____:
____
return mcs
# Check that there are 33 maximal cliques of size 3 in the graph T
assert ____ == ____