Znajdowanie wszystkich maksymalnych klik o rozmiarze "n"

Skoro zapoznałeś się już z trójkątami (i otwartymi trójkątami), czas przejść do pojęcia maksymalnych klik. Maksymalne kliki to kliki, których nie można rozszerzyć przez dodanie sąsiedniej krawędzi – są przydatną właściwością grafu podczas wykrywania społeczności. NetworkX udostępnia funkcję pozwalającą zidentyfikować węzły wchodzące w skład każdej maksymalnej kliki w grafie: nx.find_cliques(G). Poeksperymentuj z tą funkcją, wywołując ją na grafie T w powłoce IPython, a następnie spróbuj rozwiązać ćwiczenie.

Napisz funkcję maximal_cliques() przyjmującą dwa parametry – G i size – która znajduje wszystkie maksymalne kliki o rozmiarze n.
- W pętli for iteruj po wszystkich klikach w G, używając funkcji nx.find_cliques().
- Jeśli bieżąca klika ma rozmiar size, dołącz ją do listy mcs.
Użyj instrukcji assert oraz funkcji maximal_cliques(), aby sprawdzić, czy w grafie T istnieje dokładnie 33 maksymalne kliki o rozmiarze 3.

.css-6su6fj{-webkit-flex-shrink:0;-ms-flex-negative:0;flex-shrink:0;}ćwiczenie

Instrukcje

ćwiczenie