| 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)
|
| 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)
|
