Имеется таблица истинности, описывающая граф. Как определить - по этой таблице истинности (макросом или формулой) - сколько контуров в этом графе (или вообще ни одного) ?
Sub t()
i = 3
For Each cell In Range("I4:AA22")
If cell = 1 Then
Cells(i, 1) = Cells(3, cell.Column)
Cells(i, 2) = Cells(cell.Row, 8)
i = i + 1
End If
Next
End Sub
Василиса Лукьянчикова, ну как бы правила логические какие то есть или нет как это высчитывается, визуально то их видно но чтоб сварганить формулу этого мало,
Сергей написал: это все вершины по периметру соединенные линией
можно и такой аналогией воспользоваться. Но будет ли контуром линия, охватывающая две соседних области, например? А три? А граница страны на той же карте?
Имеется таблица истинности, описывающая граф. Как определить - по этой таблице истинности (макросом или формулой) - сколько контуров в этом графе (или вообще ни одного) ?
Мне кажется, что это должен быть какой-то перебор по всем представленным в таблице A3:B15 номерам вершин.
То есть сперва идет вершина 1, и проверяется - с какими вершинами она соединена. Допустим она соединена с вершиной 3. Значит дальше перебираются все вершины 3 - с кем они соединены. Допустим соединена с вершиной 10 и при дальнейшем переборе выясняется что вершина 10 имеет соединение с вершиной 1. Это означает что найден один контур и в какую-то ячейку добавляется 1 (и продолжается дальнейший поиск - пока не будут перебраны все остальные вершины).
Вот только как этот цикл (даже несколько вложенных циклов наверное) организовать - я не понимаю.
И что ответов на поставленные вопросы совсем не будет? Только дубль первого сообщения? Вариант. 1. Убираем висячие узлы - такие, что переход из такого возможен только в один узел. В примере это 9, 12 (не забываем про симметрию). Повторяем 1, пока висячих не останется. Если не осталось вообще узлов, то в графе нет контуров. 2. Если что-то осталось. убираем произвольное ребро, например 2-3. Увеличиваем счётчик контуров на 1. 2.1 Если получились висячие узлы, то повторяем 1 (например, если исключить ребро 1-8, то 8 узел станет висячим).
Если после 1 что-то осталось повторяем 2. Пока не уберём все узлы. Сколько раз повторим 2 - столько и контуров имеем в графе. Как-то так. Успехов. Обновил ниже.
P. S. Господа модераторы, может сменим название темы? Определить число циклов по матрице смежности графа.
В представленном алгоритме есть ошибка. Пусть имеем два подграфа (попросту геометрически два квадрата). Соединим ребром вершину одного подграфа с вершиной другого. Получим так называемое мостовое ребро. Его удаление не является признаком наличия контура (думаю понятно почему). Следовательно, пункт 1 нужно дополнить удалением мостовых рёбер. Updated. Можно пойти простым путём, предполагается что граф связанный, если нет, то либо разбиваем на подграфы, либо запускаем с узла с признаком не посещенный . Через обход графа в глубину. Для каждого узла устанавливаем признак - посещённый ли, для каждого ребра пройден ли. Запускаем с любого узла с признаком не посещённый (не забываем сразу его пометить посещённым). Обходим в глубину, помечая каждое пройденное ребро признаком пройдено. Естественно, по рёбрам с признаком пройдено больше не ходим. Помечаем при переходе по ребру в следующий узел этот узел посещённый. Если какой-то узел при переходе имеет признак посещённый, то увеличиваем счётчик контуров на 1. Вроде всё.