| dbo:abstract |
In mathematics, a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree if the graph does not contain a spanning tree with a smaller bottleneck edge weight. For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence (MBSA). (en) Минимально критичное остовное дерево (англ. minimum bottleneck spanning tree, MBST) во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным остовным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего веса. Для ориентированного графа аналогичная задача известна как минимально критичное стягивающее ориентированное дерево (англ. Minimum Bottleneck Spanning Arborescence, MBSA). (ru) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/MBST.png?width=300 |
| dbo:wikiPageID |
41228765 (xsd:integer) |
| dbo:wikiPageLength |
15256 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1119775563 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Robert_Tarjan dbr:Big-O_notation dbr:Algorithm dbc:Spanning_tree dbr:Harold_N._Gabow dbr:Spanning_tree dbc:Graph_algorithms dbr:Weighted_graph dbr:Dijkstra's_algorithm dbr:Fibonacci_heap dbr:Minimum_spanning_tree dbr:File:Camerini_Algorithm_1.svg dbr:File:Camerini_Algorithm_2.svg dbr:File:Camerini_Algorithm_3.svg dbr:File:Camerini_Algorithm_4.svg dbr:File:MBSA-GT-example-1.png dbr:File:MBSA-GT-example-2.png dbr:File:MBSA-GT-example-3.png dbr:File:MBSA-GT-example-4.png dbr:File:MBSA-GT-example-5.png dbr:File:MBSA-GT-example-6.png dbr:File:MBSA-GT-example-7.png dbr:File:MBSA_Example_1.png dbr:File:MBSA_Example_10.png dbr:File:MBSA_Example_11.png dbr:File:MBSA_Example_2.png dbr:File:MBSA_Example_3.png dbr:File:MBSA_Example_4.png dbr:File:MBSA_Example_5.png dbr:File:MBSA_Example_6.png dbr:File:MBSA_Example_7.png dbr:File:MBSA_Example_8.png dbr:File:MBSA_Example_9.png dbr:File:MBST.png dbr:File:Minimum_Bottleneck_Spanning_Arborescence_(MBSA).png |
| dbp:wikiPageUsesTemplate |
dbt:Math dbt:Mvar dbt:Reflist dbt:Tmath dbt:Mset |
| dct:subject |
dbc:Spanning_tree dbc:Graph_algorithms |
| gold:hypernym |
dbr:Tree |
| rdf:type |
dbo:Plant |
| rdfs:comment |
In mathematics, a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree if the graph does not contain a spanning tree with a smaller bottleneck edge weight. For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence (MBSA). (en) Минимально критичное остовное дерево (англ. minimum bottleneck spanning tree, MBST) во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным остовным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего веса. Для ориентированного графа аналогичная задача известна как минимально критичное стягивающее ориентированное дерево (англ. Minimum Bottleneck Spanning Arborescence, MBSA). (ru) |
| rdfs:label |
Minimum bottleneck spanning tree (en) Минимально критичное остовное дерево (ru) |
| owl:sameAs |
freebase:Minimum bottleneck spanning tree yago-res:Minimum bottleneck spanning tree wikidata:Minimum bottleneck spanning tree dbpedia-ru:Minimum bottleneck spanning tree https://global.dbpedia.org/id/2Nup3 |
| prov:wasDerivedFrom |
wikipedia-en:Minimum_bottleneck_spanning_tree?oldid=1119775563&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Camerini_Algorithm_1.svg wiki-commons:Special:FilePath/Camerini_Algorithm_2.svg wiki-commons:Special:FilePath/Camerini_Algorithm_3.svg wiki-commons:Special:FilePath/Camerini_Algorithm_4.svg wiki-commons:Special:FilePath/MBSA-GT-example-1.png wiki-commons:Special:FilePath/MBSA-GT-example-2.png wiki-commons:Special:FilePath/MBSA-GT-example-3.png wiki-commons:Special:FilePath/MBSA-GT-example-4.png wiki-commons:Special:FilePath/MBSA-GT-example-5.png wiki-commons:Special:FilePath/MBSA-GT-example-6.png wiki-commons:Special:FilePath/MBSA-GT-example-7.png wiki-commons:Special:FilePath/MBSA_Example_1.png wiki-commons:Special:FilePath/MBSA_Example_10.png wiki-commons:Special:FilePath/MBSA_Example_11.png wiki-commons:Special:FilePath/MBSA_Example_2.png wiki-commons:Special:FilePath/MBSA_Example_3.png wiki-commons:Special:FilePath/MBSA_Example_4.png wiki-commons:Special:FilePath/MBSA_Example_5.png wiki-commons:Special:FilePath/MBSA_Example_6.png wiki-commons:Special:FilePath/MBSA_Example_7.png wiki-commons:Special:FilePath/MBSA_Example_8.png wiki-commons:Special:FilePath/MBSA_Example_9.png wiki-commons:Special:FilePath/MBST.png wiki-commons:Special:FilePath/Minimum_Bottleneck_Spanning_Arborescence_(MBSA).png |
| foaf:isPrimaryTopicOf |
wikipedia-en:Minimum_bottleneck_spanning_tree |
| is dbo:wikiPageWikiLink of |
dbr:Matroid-constrained_number_partitioning dbr:Minimum_spanning_tree |
| is foaf:primaryTopic of |
wikipedia-en:Minimum_bottleneck_spanning_tree |
