Описание тега spanning-tree

Вопросы с тегом
Остовное дерево в связном неориентированном графе - это подграф, который включает в себя все вершины, является деревом и связан.
0 ответов

Остовное дерево с ровно a1+a2=n ребрами

Этот вопрос очень похож на этот: остовное дерево с ровно k краями Это не тот же вопрос! - Как видите, ответ на вопрос выше не тот (к моему Q).... У нас есть связанный, неориентированный граф G=(V,E) с краями, каждый из которых либо красный, либо син…
20 май '15 в 12:19
1 ответ

Собственность соседних покрывающих деревьев

Мне нужно показать, что при наличии связанного графа с различными весами для каждого ребра каждое остовное дерево (кроме минимального остовного дерева) имеет смежное остовное дерево с меньшим весом. w(T') Я застрял в доказательстве того, что каждый …
02 янв '17 в 11:51
2 ответа

Отличается ли минимальное связующее дерево продуктов от минимального совокупного дерева?

Отличается ли минимальное связующее дерево продуктов от минимального совокупного дерева? Пожалуйста, объясните (с примерами, если это возможно). Я имею в виду, что ребра, которые добавляют к минимуму, должны (?) также иметь минимальное произведение.
14 окт '13 в 11:17
0 ответов

Как напечатать вывод 8 после интернирования образца ввода?

Я знаю логику, стоящую за этим, но я не знаю, как применить это, чтобы закончить мой код для вывода 8. Способ получить 8 - сложить кратчайшие пути к каждой вершине графа. Кратчайший путь - это путь с наименьшим количеством вершин. Если есть галстук,…
24 ноя '16 в 06:23
1 ответ

Реальные приложения, в которых используется структура данных связующего дерева

Кто-нибудь из вас знает какие-либо реальные приложения, в которых используется структура данных связующего дерева?
09 фев '14 в 16:01
1 ответ

Сокращение в конце утверждения Пролога

Я столкнулся с этим разрезом, который должен возвращать true, если существует ребро AB или BA для некоторого узла B графа Graph. node(A,Graph) :- adjacent(A,_,Graph),!. Проблема в том, что я не понимаю, почему удаление этого среза повлияет на возвра…
20 янв '19 в 15:44
1 ответ

Команда "set" работает в коммутаторах cisco?

Я пытался изменить приоритет порта по умолчанию на коммутаторе cisco, и он выдал ошибку при обнаружении неверного ввода. может кто-то объяснить ошибку в этом коде! Switch# Switch#set ? <cr> Switch#set spanning-tree ? % Unrecognized command Swi…
31 июл '15 в 06:50
2 ответа

Случайные остовные деревья двудольных графов

Я работаю над созданием кода с использованием метаэвристики для нахождения хороших решений проблемы транспортировки с фиксированной зарядкой (FCTP). Проблема, которую я имею, состоит в том, чтобы сгенерировать исходное решение, основанное на поиске …
29 мар '12 в 12:13
1 ответ

Нахождение остовного дерева с использованием ровно k красных ребер в графе с ребрами, окрашенными красным / синим в линейное время

Учитывая граф G с красными и синими ребрами и константой K, разработайте детерминированный линейный алгоритм времени, который находит остовное дерево G с ровно K красными ребрами (или возвращает False если такого остовного дерева не существует). Что…
11 фев '14 в 15:27
1 ответ

Охватывающие деревья с минимальным количеством листьев

Итак, моя проблема заключается в следующем: У меня есть ненаправленный (полный) взвешенный граф G=(V,E), и я хотел бы сгенерировать все возможные остовные деревья с минимальным количеством листьев, т.е. с минимальным количеством вершин степени 1. Да…
16 янв '17 в 21:29
1 ответ

Нахождение связующего дерева, которое минимизирует сумму глубин узлов

У меня есть ненаправленный связный граф с невзвешенными ребрами. Как построить связующее дерево (решение может быть не уникальным) таким образом, чтобы сумма глубин всех узлов была минимизирована? Это, очевидно, не нахождение минимального остовного …
21 фев '13 в 18:32
2 ответа

Приведите пример того, почему IP пытается маршрутизировать связующее дерево.

Я наблюдал за выступлением Ван Якобсона, в котором он случайно заявляет, что IP пытается маршрутизировать по связующему дереву, так как в противном случае возникают циклы, которые могут быстро разрушить сеть. Затем он продолжает, что одним из недост…
27 июн '11 в 00:45
1 ответ

STP привет таймер

В STP у нас есть MAX age timer. Он говорит нам, как долго ждать превосходящего BPDU (на корневых или блокирующих портах), прежде чем он предположит, что корневой мост или ссылка не работает. Учитывая этот таймер, почему каждый мост должен также знат…
16 ноя '16 в 20:25
2 ответа

Симуляции Java Network/Tree переходят в бесконечный цикл после определенного количества узлов

Я надеюсь, что кто-то может помочь с проблемой, с которой я столкнулся. Прежде всего, я попытался удалить как можно больше кода, который не вызывал проблему. Моя проблема заключается в следующем: когда я запускаю программу, все работает идеально, по…
02 мар '15 в 22:26
1 ответ

Как протокол связующего дерева обеспечивает избыточность в пути на уровне L2?

У меня есть очень простой вопрос, связанный с протоколом Spanning Tree Protocol, как он обеспечивает избыточность в пути. Это то, что я где-то читал о STP, но я считаю, что это отключает избыточность сети. Что вы думаете, ребята? "Обратите внимание,…
28 авг '12 в 13:08
2 ответа

Cisco - самый быстрый способ достижения конвергенции STP после сбоя соединения

Я настраиваю пару коммутаторов, по одному для наших двух центров обработки данных. У нас есть пара каналов между сайтами, один из которых является выделенным частным волокном, а другой - резервным соединением со скоростью 100 Мбит / с. По причинам, …
17 апр '12 в 14:59
6 ответов

Двунаправленное остовное дерево

Я сталкивался с этим вопросом от интервью street.com Машины в очередной раз напали на королевство Сион. Королевство Сион имеет N городов и N-1 двунаправленных дорог. Дорожная сеть такова, что между любой парой городов существует уникальный путь. У М…
04 май '12 в 05:55
2 ответа

Преобразование несбалансированного дерева в остовное дерево

Как преобразовать несбалансированное дерево в (сбалансированное) остовное дерево? Предположим, у меня есть дерево (с разным (не обязательно разным) числом детей в разных узлах). Я хочу манипулировать деревом таким образом, чтобы оно превратилось в k…
15 май '11 в 22:07
1 ответ

Связующее дерево, которое минимизирует динамическую "метрику"

Давайте иметь график. Когда мы удаляем ребро, создаются 2 "машины", по одному от каждой вершины ребра. когда эти 2 машины встречаются, они останавливаются. Задача состоит в том, чтобы создать остовное дерево таким образом, чтобы сумма количества авт…
20 янв '12 в 21:27
1 ответ

Список связующего дерева из списка ребер в Python

Я пытаюсь выяснить, как напечатать список связующего дерева из заданного списка ребер. Например, если я читаю в: 0 1 2 1 0 2 1 3 Я хочу распечатать список связующего дерева: [[1], [0,2,3], [1], [1]] Я знаю, как создать список смежности с помощью код…
16 янв '17 в 22:00