WikiDer > Остовное дерево минимальной степени - Википедия

В теория графов, для связного графа ${ displaystyle G}$, а остовное дерево ${ displaystyle T}$ является подграфом ${ displaystyle G}$ с наименьшим количеством ребер, которые все еще охватывают ${ displaystyle G}$. Можно доказать ряд свойств относительно ${ displaystyle T}$. ${ displaystyle T}$ ацикличен, имеет (${ displaystyle | V | -1}$) края, где ${ displaystyle V}$ это количество вершин в ${ displaystyle G}$ и Т. Д.

А остовное дерево минимальной степени ${ displaystyle T '}$ является остовным деревом с наименьшей максимальной степенью. Вершина максимальной степени в ${ displaystyle T '}$ наименьшее среди всех возможных остовных деревьев ${ displaystyle G}$.

обнаружение остовное дерево минимальной степени NP трудна, но алгоритм локального поиска может дать дерево, максимальная степень которого не превышает максимальную степень оптимального дерева плюс один.

Видеть Связующее дерево с ограничениями по степени.

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: «Остовное дерево минимальной степени» – Новости · газеты · книги · ученый · JSTOR (Апрель 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)