Задача вроде бы на Минимальные Остовные Деревья

[sqribner48]

Skeptic

Skeptic в сообщении #975076 писал(а):

Минимальный кандидат - это граф с одним внутренним ребром и двумя граничными. Поэтому сочетание по три элемента, а не по два.

Но ведь у ребра две концевые вершины и, следовательно, может быть еще пара смежных с ним ребер (но с другой стороны)

Skeptic в сообщении #975022 писал(а):

Линейный граф - это граф, рёбра которого можно вытянуть в линию.

А что значит "ребра вытянуть в линию"? Может быть Вы подразумевали "расположить ребра на одной линии". Но тогда этому определению соответствует простая цепь. Вы это имели в виду?

Skeptic в сообщении #975076 писал(а):

Плоский граф - это граф, который можно расположить на плоскости без пересечения рёбер.

Если быть точным, граф, который можно расположить на плоскости без пересечения рёбер обычно называется планарным. Плоский граф - это уже уложенный на плоскости граф.

Skeptic в сообщении #975022 писал(а):

$N$-мерный граф - это, понятно, какой граф.

Это граф с $n$ ребрами?

[frankenstein]

Терминология теории графов богата. Но в этом топике мы не это выясняем, а решаем задачу. (Еще несколько постов не касающиеся темы и понять невозможно будет что мы тут хотели обсуждать)

[sqribner48]

frankenstein
Я согласен с Вами. Но если давать советы, то их надо четко формулировать....
... Если все-таки перейти к реберным графам, то задача сводится к поиску компонент связности, состоящих из вершин с одинаковыми весами, окруженных вершинами с меньшими весами.
Что-то похоже на задачу: дана матрица из 0 и 1. Найти квадратную(прямоугольную) подматрицу из одних единиц. Где-то видел, но не могу найти