Страницы: 1
RSS
Определить число циклов по матрице смежности графа.
 
Доброго времени суток
Есть такой вопрос.

Имеется таблица истинности, описывающая граф.
Как определить - по этой таблице истинности (макросом или формулой) - сколько контуров в этом графе (или вообще ни одного) ?
 
Цитата
Василиса Лукьянчикова написал:
сколько контуров в этом графе
как определяется контур
Лень двигатель прогресса, доказано!!!
 
Как-то так:
Код
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
 
GRIM, нет - количество контуров - это какое-то число.
Это может быть 0,1,2,3 и т.д.

Вот об этом был вопрос - как определить их количество.
 
Сергей, контур - это замкнутый путь - который как бы совершает полный круг, по вершинам графа.
 
Василиса Лукьянчикова, ну как бы правила логические какие то есть или нет как это высчитывается, визуально то их видно но чтоб сварганить формулу этого мало,  
Лень двигатель прогресса, доказано!!!
 
Цитата
Сергей написал:
визуально то их видно
Да как сказать, Сергей, для этого нужно чёткое определение контура. Привидится может всякое :)
Изменено: Андрей VG - 08.04.2019 06:46:52
 
Андрей VG,  :D  ну я по привычке контурную карту вспоминаю для меня это все вершины по периметру соединенные линией
Лень двигатель прогресса, доказано!!!
 
Цитата
Сергей написал:
ну я по привычке контурную карту вспоминаю для меня это все вершины по периметру соединенные линией
Да - это вершины соединенные по периметру.
 
Цитата
Сергей написал:
это все вершины по периметру соединенные линией
можно и такой аналогией воспользоваться. Но будет ли контуром линия, охватывающая две соседних области, например? А три? А граница страны на той же карте?
 
Василиса Лукьянчикова, Никаких противопоказаний, но просто интересно, что вдруг переметнулись из мив сюда?
По вопросам из тем форума, личку не читаю.
 
вдруг пригодится Joseph Kirk: Count Loops in a Graph
Изменено: Андрей Лящук - 08.04.2019 09:20:00
 
Андрей Лящук, нет такого слова - пригодиццо.
 
offtop
 
Скрытый текст
Лень двигатель прогресса, доказано!!!
 
Цитата
Василиса Лукьянчикова написал:
Да - это вершины соединенные по периметру.
О, пропустил - по периметру чего?
 
Цитата
Андрей VG написал:
по периметру чего?
что непонятного по периметру периметра  :)  
Лень двигатель прогресса, доказано!!!
 
Off
Цитата
Андрей Лящук написал:
могу с вами поделиццо  
и до бана докатиццоться.
Изменено: БМВ - 08.04.2019 12:02:50
По вопросам из тем форума, личку не читаю.
 
Доброго времени суток
Есть такой вопрос.

Имеется таблица истинности, описывающая граф.
Как определить - по этой таблице истинности (макросом или формулой) - сколько контуров в этом графе (или вообще ни одного) ?
 
Мне кажется, что это должен быть какой-то перебор по всем представленным в таблице 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. Господа модераторы, может сменим название темы?
Определить число циклов по матрице смежности графа.
Изменено: Андрей VG - 09.04.2019 10:30:26
 
Андрей VG, а как примерно хотя бы - должен в виде макроса выглядеть этот алгоритм ?
Хотя бы чтобы анализировал граф - всего из 4 вершин.
 
В представленном алгоритме есть ошибка. Пусть имеем два подграфа (попросту геометрически два квадрата). Соединим ребром вершину одного подграфа с вершиной другого. Получим так называемое мостовое ребро. Его удаление не является признаком наличия контура (думаю понятно почему). Следовательно, пункт 1 нужно дополнить удалением мостовых рёбер.
Updated.
Можно пойти простым путём, предполагается что граф связанный, если нет, то либо разбиваем на подграфы, либо запускаем с узла с признаком не посещенный . Через обход графа в глубину.
Для каждого узла устанавливаем признак - посещённый ли, для каждого ребра пройден ли.
Запускаем с любого узла с признаком не посещённый (не забываем сразу его пометить посещённым). Обходим в глубину, помечая каждое пройденное ребро признаком пройдено. Естественно, по рёбрам с признаком пройдено больше не ходим. Помечаем при переходе по ребру в следующий узел этот узел посещённый. Если какой-то узел при переходе имеет признак посещённый, то увеличиваем счётчик контуров на 1.
Вроде всё.
Изменено: Андрей VG - 09.04.2019 10:40:18
 
Андрей VG, ясно.
 
Цитата
Василиса Лукьянчикова написал:
ясно.
Вот и чудно.
Вариант реализации.
 
Андрей VG, спасибо.
Буду изучать.
Страницы: 1
Наверх