Это звучит как домашнее задание, поэтому вот несколько советов: определение подграфа состоит в том, что он состоит из подмножества узлов графа и из подмножества этих ребер из исходного графа, которые проходят между выбранными узлами , (Изменить: мой первоначальный ответ был ошибочным, так как «подмножество» отсутствовало.) Другими словами, вопрос «сколько подграфов есть» имеет тот же ответ, что и «каким образом мы можем выбрать подмножества узлы ", что по сути является тем же вопросом, что и" при заданном наборе V , сколько существует подмножеств V"? Редактировать: Таким образом, как @andrew cooke указывает Несмотря на то, что просто выразить, сколько существует возможных подмножеств узлов, число возможных подмножеств ребер для каждого подмножества узлов зависит от структуры графа, поэтому для этого не существует простой формулы.