Spanning tree (original) (raw)

About DBpedia

في مجال نظرية المخططات، الشجرة المتفرعة (بالإنجليزية: spanning tree)‏ هي مخطط بياني يضم مجموعة من العقد والحواف التي تسمى أغصاناً، تتصل هذه العقد مع بعضها البعض بشكل متفرع من نقطة مركزية تسمى الجذر.

thumbnail

Property Value
dbo:abstract في مجال نظرية المخططات، الشجرة المتفرعة (بالإنجليزية: spanning tree)‏ هي مخطط بياني يضم مجموعة من العقد والحواف التي تسمى أغصاناً، تتصل هذه العقد مع بعضها البعض بشكل متفرع من نقطة مركزية تسمى الجذر. (ar) Al camp matemàtic de la teoria de grafs, un arbre d'expansió (spanning tree, en anglès) d'un graf connex és un subconjunt de les arestes del graf que és acíclic i connecta tots els vèrtexs del graf. En general, un graf pot tenir més d'un arbre d'expansió, però un graf que no sigui connex no pot contenir cap arbre d'expansió. Si totes les arestes de G són també arestes d'un arbre d'expansió T de G, llavors G és un arbre i és idèntic a T (és a dir, un arbre té un únic arbre d'expansió i és el mateix graf). Un arbre d'expansió d'un graf d'ordre n té exactament n-1 arestes. Un arbre d'expansió d'un graf connex G pot també ésser definit com el conjunt màxim d'arestes de G que no contenen cicles, o com el conjunt mínim d'arestes que connecten tots els vèrtexs. (ca) V teorii grafů je kostra souvislého grafu G takový podgraf souvislého grafu G na množině všech jeho vrcholů, který je stromem. (cs) Ein Spannbaum (auch aufspannender Baum oder Gerüst genannt; englisch spanning tree, manchmal fälschlich als „spannender Baum“ übersetzt) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten dieses Graphen enthält. Spannbäume existieren nur in zusammenhängenden Graphen. In einem vollständigen Graphen findet man nach der Cayley-Formel verschiedene Spannbäume. Im nebenstehenden Beispiel des sind es Stück. (de) Dans le domaine mathématique de la théorie des graphes, un arbre couvrant d'un graphe non orienté et connexe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe. De façon équivalente, c'est un sous-graphe acyclique maximal, ou encore, un sous-graphe couvrant connexe minimal. (fr) En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T. Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices. En ciertos campos de la teoría de grafos es útil encontrar el mínimo árbol de expansión de un grafo ponderado. También se han abordado otros problemas de optimización relacionados con los árboles de expansión, como el máximo árbol de expansión, el máximo árbol que cubre al menos k vértices, el mínimo árbol de expansión con k aristas por vértice como máximo (árbol de expansión de mínimo grado, MDST por sus siglas en inglés), el árbol de expansión con el máximo número de hojas (estrechamente relacionado con el problema del menos conjunto dominante y conexo), el árbol de expansión con el menor número de hojas (relacionado con el problema del camino hamiltoniano), el árbol de expansión de mínimo diámetro o el árbol de expansión de la mínima dilación. (es) In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself). (en) 그래프 이론에서 신장 부분 그래프(身長部分graph, 영어: spanning subgraph 스패닝 서브그래프[*]) 또는 생성 부분 그래프(生成部分graph)는 모든 꼭짓점을 포함하는 부분 그래프이다. (ko) 全域木（ぜんいきぎ、英: Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、グラフ理論において、以下のように定義される木のことである。 グラフ G(V,E) において T ⊆ E となる辺集合 T があるとき、グラフ S(V,T) が木（閉路を持たないグラフ）であるなら、 S(V,T) のことをグラフ G(V,E) の全域木であるとする。 つまり、あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のことである。 (ja) 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. (pl) Un albero ricoprente (anche detto di copertura, di connessione o di supporto) di un grafo, connesso e con archi non orientati, è un albero che contiene tutti i vertici del grafo e contiene soltanto un sottoinsieme degli archi, cioè solo quelli necessari per connettere tra loro tutti i vertici con uno e un solo cammino. Infatti ciò che differenzia un grafo da un albero è che in quest'ultimo non sono presenti cammini multipli tra due nodi, nell'immagine sono mostrati in grassetto gli archi che fanno parte di un albero ricoprente mentre gli archi del grafo originario erano tutti gli archi, sia quelli in grassetto sia quelli sottili. L'albero ricoprente è anche noto con il termine inglese spanning tree (ST). (it) Uma árvore de extensão ou árvore de dispersão (em inglês: spanning tree) é o subconjunto de arestas de um grafo que forma uma árvore contendo todos os vértices. Uma árvore de extensão mínima ou árvore de extensão de custo mínimo (em inglês: minimum spanning tree) é o subconjunto de arestas de menor peso total em um grafo valorado que forma uma árvore contendo todos os nós. Uma árvore de extensão/dispersão apresenta as seguintes propriedades: * Define um subconjunto de arestas que mantém o grafo conectado em um único componente; * Em um grafo não-valorado qualquer árvore de dispersão é mínima; * Podem ser calculadas em tempo polinomial. Os algoritmos usuais para a determinação de árvores de extensão/dispersão são o algoritmo de Prim (1957) e o algoritmo de Kruskal (1956). (pt) Кістякове дерево (англ. Spanning tree) зв'язаного неорієнтованого графа — ациклічний (тобто, не має циклів) зв'язний підграф цього графа, який містить всі його вершини. Неформально кажучи, кістякове дерево складається з деякої підмножини ребер графа, таких, що рухаючись цими ребрами можна з будь-якої вершини графа потрапити до будь-якої іншої. Кістякове дерево також називають каркасним деревом, [джерело?], кістяком або каркасом графа. (uk) О́стовное де́рево графа (англ. Spanning tree) — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа. Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все вершин исходного графа и содержит ребро. (ru) 在图论中，無向圖 G 的生成树（英語：Spanning Tree）是具有 G 的全部顶点，但边数最少的連通子圖。 以表示顶点，表示边，若图 和树，有和，那么是的生成树。 一个图的生成树可能有多个。 (zh)
dbo:thumbnail wiki-commons:Special:FilePath/4x4_grid_spanning_tree.svg?width=300
dbo:wikiPageID 455770 (xsd:integer)
dbo:wikiPageLength 26260 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1121900925 (xsd:integer)
dbo:wikiPageWikiLink dbc:Axiom_of_choice dbr:Queue_(abstract_data_type) dbr:Multigraph dbr:Determinant dbc:Spanning_tree dbr:Hypercube_graph dbr:Pathfinding dbr:Cycle_(graph_theory) dbr:Cycle_basis dbr:Cycle_space dbr:Undirected_graph dbr:Delaunay_triangulation dbr:Depth-first_search dbr:Invariant_(mathematics) dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Connected_graph dbr:Mathematics dbr:Matrix_(mathematics) dbr:Genus_(mathematics) dbr:Telecommunications_network dbr:Linear_time dbr:Choice_function dbr:Singular_matrix dbr:Stack_(abstract_data_type) dbr:Computational_complexity_theory dbr:Hamiltonian_path_problem dbr:Maximum_leaf_spanning_tree dbr:Minimum_degree_spanning_tree dbr:Matroid dbr:Cayley's_formula dbr:Tree_(graph_theory) dbr:Data_link_layer dbr:Weighted_graph dbr:Dual_matroid dbr:Laplacian_matrix dbr:Link-state_routing_protocol dbr:Trémaux_tree dbr:A*_search_algorithm dbr:Cycle_graph dbr:Edge_(graph_theory) dbr:Euclidean_minimum_spanning_tree dbr:Breadth-first_search dbr:Family_of_sets dbr:Flooding_algorithm dbr:Good_spanning_tree dbr:Graph_embedding dbr:Graph_theory dbr:Graphic_matroid dbr:Random dbc:Computational_problems_in_graph_theory dbr:Edge_contraction dbr:Zorn's_lemma dbr:Dijkstra's_algorithm dbr:Augmented_tree-based_routing dbr:Axiom_of_choice dbr:Bond_graph dbr:Planar_graph dbr:Spanning_Tree_Protocol dbr:Connected_component_(graph_theory) dbr:Polynomial_time dbr:Approximation_ratio dbr:Mesh_topology dbr:Minimum_spanning_tree dbr:Open_Shortest_Path_First dbr:Kirchhoff's_theorem dbr:Vertex_(graph_theory) dbr:Tutte_polynomial dbr:Euclidean_plane dbr:Routing_loop dbr:Uniform_spanning_tree dbr:Sharp-P-complete dbr:Topological_graph_theory dbr:Random_minimal_spanning_tree dbr:Xuong_tree dbr:Bridge_loop dbr:File:Cayley's_formula_2-4.svg dbr:File:4x4_grid_spanning_tree.svg
dbp:wikiPageUsesTemplate dbt:About dbt:Authority_control dbt:Harvtxt dbt:Main dbt:Math dbt:Reflist dbt:Short_description
dcterms:subject dbc:Axiom_of_choice dbc:Spanning_tree dbc:Computational_problems_in_graph_theory
gold:hypernym dbr:Subgraph
rdf:type owl:Thing yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659
rdfs:comment في مجال نظرية المخططات، الشجرة المتفرعة (بالإنجليزية: spanning tree)‏ هي مخطط بياني يضم مجموعة من العقد والحواف التي تسمى أغصاناً، تتصل هذه العقد مع بعضها البعض بشكل متفرع من نقطة مركزية تسمى الجذر. (ar) V teorii grafů je kostra souvislého grafu G takový podgraf souvislého grafu G na množině všech jeho vrcholů, který je stromem. (cs) Ein Spannbaum (auch aufspannender Baum oder Gerüst genannt; englisch spanning tree, manchmal fälschlich als „spannender Baum“ übersetzt) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten dieses Graphen enthält. Spannbäume existieren nur in zusammenhängenden Graphen. In einem vollständigen Graphen findet man nach der Cayley-Formel verschiedene Spannbäume. Im nebenstehenden Beispiel des sind es Stück. (de) Dans le domaine mathématique de la théorie des graphes, un arbre couvrant d'un graphe non orienté et connexe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe. De façon équivalente, c'est un sous-graphe acyclique maximal, ou encore, un sous-graphe couvrant connexe minimal. (fr) In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself). (en) 그래프 이론에서 신장 부분 그래프(身長部分graph, 영어: spanning subgraph 스패닝 서브그래프[*]) 또는 생성 부분 그래프(生成部分graph)는 모든 꼭짓점을 포함하는 부분 그래프이다. (ko) 全域木（ぜんいきぎ、英: Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、グラフ理論において、以下のように定義される木のことである。 グラフ G(V,E) において T ⊆ E となる辺集合 T があるとき、グラフ S(V,T) が木（閉路を持たないグラフ）であるなら、 S(V,T) のことをグラフ G(V,E) の全域木であるとする。 つまり、あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のことである。 (ja) Кістякове дерево (англ. Spanning tree) зв'язаного неорієнтованого графа — ациклічний (тобто, не має циклів) зв'язний підграф цього графа, який містить всі його вершини. Неформально кажучи, кістякове дерево складається з деякої підмножини ребер графа, таких, що рухаючись цими ребрами можна з будь-якої вершини графа потрапити до будь-якої іншої. Кістякове дерево також називають каркасним деревом, [джерело?], кістяком або каркасом графа. (uk) О́стовное де́рево графа (англ. Spanning tree) — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа. Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все вершин исходного графа и содержит ребро. (ru) 在图论中，無向圖 G 的生成树（英語：Spanning Tree）是具有 G 的全部顶点，但边数最少的連通子圖。 以表示顶点，表示边，若图 和树，有和，那么是的生成树。 一个图的生成树可能有多个。 (zh) Al camp matemàtic de la teoria de grafs, un arbre d'expansió (spanning tree, en anglès) d'un graf connex és un subconjunt de les arestes del graf que és acíclic i connecta tots els vèrtexs del graf. En general, un graf pot tenir més d'un arbre d'expansió, però un graf que no sigui connex no pot contenir cap arbre d'expansió. Si totes les arestes de G són també arestes d'un arbre d'expansió T de G, llavors G és un arbre i és idèntic a T (és a dir, un arbre té un únic arbre d'expansió i és el mateix graf). Un arbre d'expansió d'un graf d'ordre n té exactament n-1 arestes. (ca) En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T. (es) Un albero ricoprente (anche detto di copertura, di connessione o di supporto) di un grafo, connesso e con archi non orientati, è un albero che contiene tutti i vertici del grafo e contiene soltanto un sottoinsieme degli archi, cioè solo quelli necessari per connettere tra loro tutti i vertici con uno e un solo cammino. Infatti ciò che differenzia un grafo da un albero è che in quest'ultimo non sono presenti cammini multipli tra due nodi, nell'immagine sono mostrati in grassetto gli archi che fanno parte di un albero ricoprente mentre gli archi del grafo originario erano tutti gli archi, sia quelli in grassetto sia quelli sottili. (it) Uma árvore de extensão ou árvore de dispersão (em inglês: spanning tree) é o subconjunto de arestas de um grafo que forma uma árvore contendo todos os vértices. Uma árvore de extensão mínima ou árvore de extensão de custo mínimo (em inglês: minimum spanning tree) é o subconjunto de arestas de menor peso total em um grafo valorado que forma uma árvore contendo todos os nós. Uma árvore de extensão/dispersão apresenta as seguintes propriedades: Os algoritmos usuais para a determinação de árvores de extensão/dispersão são o algoritmo de Prim (1957) e o algoritmo de Kruskal (1956). (pt) 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 (pl)
rdfs:label Spanning tree (en) شجرة متفرعة (ar) Arbre d'expansió (ca) Kostra grafu (cs) Spannbaum (de) Árbol de expansión (es) Arbre couvrant (fr) Albero ricoprente (it) 신장 부분 그래프 (ko) 全域木 (ja) Drzewo rozpinające (pl) Árvore de extensão (pt) Остовное дерево (ru) Кістякове дерево (uk) 生成树 (zh)
owl:sameAs freebase:Spanning tree yago-res:Spanning tree wikidata:Spanning tree dbpedia-ar:Spanning tree dbpedia-ca:Spanning tree dbpedia-cs:Spanning tree dbpedia-da:Spanning tree dbpedia-de:Spanning tree dbpedia-es:Spanning tree dbpedia-fa:Spanning tree dbpedia-fi:Spanning tree dbpedia-fr:Spanning tree dbpedia-he:Spanning tree dbpedia-hr:Spanning tree dbpedia-hu:Spanning tree dbpedia-it:Spanning tree dbpedia-ja:Spanning tree dbpedia-ko:Spanning tree http://lt.dbpedia.org/resource/Aprėpties_medis dbpedia-no:Spanning tree dbpedia-pl:Spanning tree dbpedia-pt:Spanning tree dbpedia-ru:Spanning tree dbpedia-sk:Spanning tree dbpedia-sl:Spanning tree dbpedia-sr:Spanning tree dbpedia-th:Spanning tree dbpedia-uk:Spanning tree dbpedia-vi:Spanning tree dbpedia-zh:Spanning tree https://global.dbpedia.org/id/4zTM9
prov:wasDerivedFrom wikipedia-en:Spanning_tree?oldid=1121900925&ns=0
foaf:depiction wiki-commons:Special:FilePath/4x4_grid_spanning_tree.svg wiki-commons:Special:FilePath/Cayley's_formula_2-4.svg
foaf:isPrimaryTopicOf wikipedia-en:Spanning_tree
is dbo:wikiPageDisambiguates of dbr:Spanning_tree_(disambiguation)
is dbo:wikiPageRedirects of dbr:Spanning_Tree dbr:Spanning_Tree_(mathematics) dbr:Spanning_forest dbr:Spanning_tree_(Mathematics) dbr:Fundamental_cutset dbr:Fundamental_cycle dbr:Spanning_tree_(mathematics) dbr:Spanning_tree_(networks)
is dbo:wikiPageWikiLink of dbr:Catalan's_constant dbr:Quantum_complexity_theory dbr:End_(graph_theory) dbr:Mac_Lane's_planarity_criterion dbr:209_(number) dbr:Determinant dbr:Hypercube_graph dbr:List_of_books_in_computational_geometry dbr:Cycle_basis dbr:Determinantal_point_process dbr:Ear_decomposition dbr:Independence_Theory_in_Combinatorics dbr:Positional_game dbr:Comparison_of_audio_network_protocols dbr:Complete_bipartite_graph dbr:Crispin_Nash-Williams dbr:Matrix_of_ones dbr:Matroid_parity_problem dbr:Gas_networks_simulation dbr:Nash-Williams_theorem dbr:Net_(polyhedron) dbr:Schreier_coset_graph dbr:Generating_function dbr:Glossary_of_graph_theory dbr:Graph_of_groups dbr:Bouquet_graph dbr:Möbius_ladder dbr:Connected_dominating_set dbr:Convex_hull dbr:Combinatorial_optimization dbr:Deletion–contraction_formula dbr:Feedback_arc_set dbr:Feedback_vertex_set dbr:Fundamental_group dbr:Kruskal's_algorithm dbr:Minimum_degree_spanning_tree dbr:Spanning_tree_(disambiguation) dbr:Markov_chain_tree_theorem dbr:Matroid-constrained_number_partitioning dbr:Matroid_oracle dbr:Matroid_partitioning dbr:Cayley's_formula dbr:Tree_(graph_theory) dbr:Wagner_graph dbr:Wheel_graph dbr:Distributed_algorithm dbr:Laman_graph dbr:Minimum_routing_cost_spanning_tree dbr:Trémaux_tree dbr:Dual_graph dbr:Brooks'_theorem dbr:Pairwise_independence dbr:Daniela_Kühn dbr:Discrete_uniform_distribution dbr:Flooding_algorithm dbr:Good_spanning_tree dbr:Graph_Theory,_1736–1936 dbr:Graph_homology dbr:Graph_theory dbr:Graphic_matroid dbr:Tatyana_Pavlovna_Ehrenfest dbr:Jack_Edmonds dbr:Covering_graph dbr:OPTICS_algorithm dbr:Abelian_sandpile_model dbr:Laves_graph dbr:Edge_contraction dbr:Distance-hereditary_graph dbr:Dominating_set dbr:Douglas_McIlroy dbr:Axiom_of_choice dbr:Spanning_Tree dbr:Circulant_graph dbr:Greedy_embedding dbr:Grid_bracing dbr:Minimum_bottleneck_spanning_tree dbr:Minimum_spanning_tree dbr:Network_Time_Protocol dbr:Klam_value dbr:Loop-erased_random_walk dbr:Multicast dbr:Multiple_Spanning_Tree_Protocol dbr:Shortest-path_tree dbr:Nielsen–Schreier_theorem dbr:FKT_algorithm dbr:IEEE_802.1aq dbr:Prism_graph dbr:Planarization dbr:The_Mathematics_of_Chip-Firing dbr:Spanning_Tree_(mathematics) dbr:Spanning_forest dbr:Spanning_tree_(Mathematics) dbr:Whitney's_planarity_criterion dbr:Topological_graph dbr:Nonblocker dbr:Pfaffian_orientation dbr:Reverse-search_algorithm dbr:Topology_(electrical_circuits) dbr:Sparsity_matroid dbr:Xuong_tree dbr:Fundamental_cutset dbr:Fundamental_cycle dbr:Spanning_tree_(mathematics) dbr:Spanning_tree_(networks)
is foaf:primaryTopic of wikipedia-en:Spanning_tree