Drzewo rozpinające
Sign in to savesubgraph of an undirected graph G that is a tree which includes all of the vertices of G
Wikidata facts
- Image
- Spanning tree - version 1.jpg
Show 4 more facts
- topic's main category
- Category:Spanning tree
- Commons category
- Spanning trees
- studied by
- graph theory
- maintained by WikiProject
- WikiProject Mathematics
Sources (3)
via Wikidata · CC0
Article · Polski
Drzewo rozpinające (ang. Spanning Tree) – drzewo, które zawiera wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu. Konstrukcja drzewa rozpinającego polega na usuwaniu z grafu tych krawędzi, które należą do cykli. Najmniejszą liczbę krawędzi jaką trzeba usunąć z grafu, aby graf stał się acykliczny (stał się drzewem) nazywa się rzędem acykliczności grafu lub liczbą cyklometryczną. * Drzewo rozpinające (czerwone krawędzie) w grafie * Inne drzewo rozpinające w tym samym grafie Drzewo rozpinające można znaleźć przykładowo wykorzystując algorytm DFS lub Dijkstry.
Abstract from DBpedia / Wikipedia · CC BY-SA