Это может звучать глупо, но возможно ли иметь случай, когда число двусвязных компонентов графа превышает число вершин в графе?
Я считаю, что это невозможно и может быть быстро проверенос небольшими графиками.
Вот основная логическая попытка объяснить, почему это невозможно. Интуиция, если мы продолжим добавлять ребра к графу в надежде, что это увеличит число компонентов с двойным соединением, наоборот, уменьшит количество компонентов, так какподключит больше компонентов, которые ранее не были подключены. Вследствие этого максимальное количество двусвязных компонентов может быть получено из древовидного структурированного графа (поскольку он имеет минимальное количество ребер, оставаясь при этом связанным) (при условии, что каждое ребро считается двусвязным компонентом). В дереве максимальное число ребер может быть n-1, где n - количество вершин, и это приводит к утверждению, что
" Максимальное количество двусвязных компонентов будет n-1 длялюбой график"
Может кто-нибудь помочь мне подтвердить это предложение, пожалуйста?