ПочатиПочніть безкоштовно

Пошук усіх максимальних клік розміру «n»

Тепер, коли ви розібралися з трикутниками (і відкритими трикутниками), перейдемо до поняття максимальних клік. Максимальні кліки — це кліки, які не можна розширити додаванням суміжного ребра, і це корисна властивість графа під час пошуку спільнот. У NetworkX є функція, яка дозволяє визначити вузли, що входять до кожної максимальної кліки в графі: nx.find_cliques(G). Спробуйте цю функцію на T в IPython Shell, а потім виконайте вправу.

Ця вправа є частиною курсу

Вступ до аналізу мереж у Python

Переглянути курс

Інструкції до вправи

  • Напишіть функцію maximal_cliques(), яка має два параметри — G і size — і знаходить усі максимальні кліки розміру n.
    • У циклі for ітеруйте всі кліки в G, використовуючи функцію nx.find_cliques().
    • Якщо поточна кліка має розмір size, додайте її до списку mcs.
  • Використайте оператор assert і вашу функцію maximal_cliques(), щоб перевірити, що в графі T є 33 максимальні кліки розміру 3.

Інтерактивна практична вправа

Спробуйте виконати цю вправу, доповнивши цей зразок коду.

# 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 ____ == ____
Редагувати та запускати код