Теория графов

[Астасья]

связан ли ацикличный граф с 10-ю вершинами и 9-ю рёбрами???почему???

[holloloh]

Видимо нет, но вот как это математически объяснить...
по сути, чтобы граф с n вершинами и n-1 связями был связным, он должен выглядеть вот так
Но этот граф цикличен.
Осталось доказать что при любых других конфигурациях граф не будет связным.
Как это доказать я не знаю.

[Астасья]

связный ацикличный граф -дерево,но вот почему такое может быть???

[holloloh]

Да, я туплю, такое спокойно может быть.
Мы из любой точки графа можем достигнуть любой другой, и мы не можем нарисовать путь, в котором мы могли бы вернуться в уже посещенную точку, т.е он ацикличен.
Значит всё хорошо :3

[Астасья]