| dbo:abstract
|
- يقال أن مخططاً موجهاً ما قوي التوصيل (بالإنجليزية: strongly connected)، إذا وجد مسلك أو طريق من كل عقدة في المخطط يوصل إلى أي نقطة أخرى. وإذا فسرنا ذلك من ناحية الرياضيات فإن هذه الخاصية تترجم بأن المصفوفة التابعة لهذا المخطط تكون غير قابلة للاختزال أي (irreducible) أي أن أي قوة للمصفوفة تعطي مصفوفة ليست صفرا. (ar)
- Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů u, v existuje sled. (cs)
- En teoria de grafs, un graf dirigit és fortament connex si per a cada parell de vèrtexs u i v hi ha un camí de u cap a v i un camí de v cap a u. Els components fortament connexos (CFC) d'un graf dirigit són els seus subgrafs màxims fortament connexos. Aquests subgrafs formen una partició del graf. Un subgraf fortament connex és màxim si conté tots els vèrtexs del graf o si en afegir-hi un vèrtex més del graf deixa de ser fortament connex. El càlcul dels components fortament connexos d'un graf és un dels problemes fonamentals de la teoria dels grafs. El primer algorisme que treballa en temps lineal per a resoldre aquest problema va ser proposat per Robert Tarjan el 1970 a base d'una cerca en profunditat (depth-first search). Altres algorismes apareixen en els principals textos d'algorísmica. La complexitat d'aquest algorisme és O (V+E). (ca)
- En teoría de grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus subgrafos maximales fuertemente conexos. Estos subgrafos forman una partición del grafo. Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo. El cálculo de los componentes fuertemente conexos de un grafo es uno de los problemas fundamentales de la Teoría de los grafos. El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan en 1970 a base de una búsqueda en profundidad (depth-first search). Otros algoritmos aparecen en los principales textos sobre algorítmica. La complejidad de este algoritmo es O(V+E). (es)
- En théorie des graphes, une composante fortement connexe d'un graphe orienté G est un sous-graphe de G possédant la propriété suivante, et qui est maximal pour cette propriété : pour tout couple (u, v) de nœuds dans ce sous-graphe, il existe un chemin de u à v. Un graphe est dit fortement connexe s'il est formé d'une seule composante fortement connexe. De manière générale, un graphe se décompose de manière unique comme union de composantes fortement connexes deux à deux disjointes. (fr)
- In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)). (en)
- 유향 그래프에서 모든 정점이 모든 다른 정점에 대해 도달 가능한 경우, 그래프는 강하게 연결되었다 또는 상호연결되었다라고 한다. 강한 연결 요소 또는 상호연결요소는 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향그래프의 분할이다. 그래프가 강하게 연결되었는지와 그래프에서 강한 연결 요소를 찾는것은 선형 시간(Θ(V+E))에 가능하다 . (ko)
- Una componente fortemente connessa di un grafo diretto G è un sottografo massimale di G in cui esiste un cammino orientato tra ogni coppia di nodi ad esso appartenenti. Le componenti fortemente connesse formano una partizione di G poiché un nodo non può trovarsi contemporaneamente in due componenti fortemente connesse, di conseguenza un grafo diretto è fortemente connesso se e solo se ha una sola componente fortemente connessa. Due vertici di G sono fortemente connessi se e solo se fanno parte dello stesso ciclo orientato. (it)
- Ориентированный граф (орграф) называется сильно связным (англ. strongly connected), если любые две его вершины s и t сильно связны, то есть если существует ориентированный путь из в и одновременно ориентированный путь из в Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы. Областью сильной связности называется множество вершин компонентов сильной связности. (ru)
- Silnie spójna składowa (SSS) grafu skierowanego G to taki maksymalny podgraf H, a jednocześnie jego spójna składowa, taka, że pomiędzy każdymi dwoma jej wierzchołkami istnieje ścieżka. Innymi słowy, w silnie spójnej składowej da się dojść z każdego jej wierzchołka do każdego innego. Dla grafu nieskierowanego każda spójna składowa będzie silnie spójna. (pl)
- Орієнтований граф називається сильно зв'язним, якщо існує шлях з будь-якої вершини графа до кожної з інших вершин. Зокрема, це означає наявність шляхів в обох напрямках: з a в b і з b в a. Компонента сильної зв'язності орієнтованого графа G — це найбільший сильно зв'язаний підграф. Якщо кожну компонента сильної зв'язності стягнути до однієї вершини, отримаємо орієнтований ациклічний граф, ущільнення (англ. condensation) G. Орієнтований граф є ациклічним тоді і лише тоді, коли він не має компонент сильної зв'язності з більш як однією вершиною, бо орієнтований цикл є сильно зв'язним і кожна нетривіальна компонента сильної зв'язності містить щонайменше один орієнтований цикл. Алгоритм Косараджу, алгоритм Тар'яна і всі дієво знаходять компоненти сильної зв'язності орієнтованого графа, але алгоритм Тар'яна і алгоритм базований на шляхах сприятливіші на практиці, бо вони потребують лише один пошук у глибину замість двох. Відповідно до теореми Роббінса, неорієнтований граф можна зорієнтувати таким чином, що він стане сильно зв’язним, тоді і тільки тоді, коли він 2-реберно-зв'язний. (uk)
- 在有向图的数学理论中，如果一个图的每一个顶点都可从该图其他任意一点到达，则称该图是强连通的。在任意有向图中能够实现强连通的部分我们称其为强连通分量。判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间（Θ(V + E)）。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12870 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- يقال أن مخططاً موجهاً ما قوي التوصيل (بالإنجليزية: strongly connected)، إذا وجد مسلك أو طريق من كل عقدة في المخطط يوصل إلى أي نقطة أخرى. وإذا فسرنا ذلك من ناحية الرياضيات فإن هذه الخاصية تترجم بأن المصفوفة التابعة لهذا المخطط تكون غير قابلة للاختزال أي (irreducible) أي أن أي قوة للمصفوفة تعطي مصفوفة ليست صفرا. (ar)
- Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů u, v existuje sled. (cs)
- En théorie des graphes, une composante fortement connexe d'un graphe orienté G est un sous-graphe de G possédant la propriété suivante, et qui est maximal pour cette propriété : pour tout couple (u, v) de nœuds dans ce sous-graphe, il existe un chemin de u à v. Un graphe est dit fortement connexe s'il est formé d'une seule composante fortement connexe. De manière générale, un graphe se décompose de manière unique comme union de composantes fortement connexes deux à deux disjointes. (fr)
- In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)). (en)
- 유향 그래프에서 모든 정점이 모든 다른 정점에 대해 도달 가능한 경우, 그래프는 강하게 연결되었다 또는 상호연결되었다라고 한다. 강한 연결 요소 또는 상호연결요소는 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향그래프의 분할이다. 그래프가 강하게 연결되었는지와 그래프에서 강한 연결 요소를 찾는것은 선형 시간(Θ(V+E))에 가능하다 . (ko)
- Una componente fortemente connessa di un grafo diretto G è un sottografo massimale di G in cui esiste un cammino orientato tra ogni coppia di nodi ad esso appartenenti. Le componenti fortemente connesse formano una partizione di G poiché un nodo non può trovarsi contemporaneamente in due componenti fortemente connesse, di conseguenza un grafo diretto è fortemente connesso se e solo se ha una sola componente fortemente connessa. Due vertici di G sono fortemente connessi se e solo se fanno parte dello stesso ciclo orientato. (it)
- Ориентированный граф (орграф) называется сильно связным (англ. strongly connected), если любые две его вершины s и t сильно связны, то есть если существует ориентированный путь из в и одновременно ориентированный путь из в Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы. Областью сильной связности называется множество вершин компонентов сильной связности. (ru)
- Silnie spójna składowa (SSS) grafu skierowanego G to taki maksymalny podgraf H, a jednocześnie jego spójna składowa, taka, że pomiędzy każdymi dwoma jej wierzchołkami istnieje ścieżka. Innymi słowy, w silnie spójnej składowej da się dojść z każdego jej wierzchołka do każdego innego. Dla grafu nieskierowanego każda spójna składowa będzie silnie spójna. (pl)
- 在有向图的数学理论中，如果一个图的每一个顶点都可从该图其他任意一点到达，则称该图是强连通的。在任意有向图中能够实现强连通的部分我们称其为强连通分量。判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间（Θ(V + E)）。 (zh)
- En teoria de grafs, un graf dirigit és fortament connex si per a cada parell de vèrtexs u i v hi ha un camí de u cap a v i un camí de v cap a u. Els components fortament connexos (CFC) d'un graf dirigit són els seus subgrafs màxims fortament connexos. Aquests subgrafs formen una partició del graf. Un subgraf fortament connex és màxim si conté tots els vèrtexs del graf o si en afegir-hi un vèrtex més del graf deixa de ser fortament connex. La complexitat d'aquest algorisme és O (V+E). (ca)
- En teoría de grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus subgrafos maximales fuertemente conexos. Estos subgrafos forman una partición del grafo. Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo. La complejidad de este algoritmo es O(V+E). (es)
- Орієнтований граф називається сильно зв'язним, якщо існує шлях з будь-якої вершини графа до кожної з інших вершин. Зокрема, це означає наявність шляхів в обох напрямках: з a в b і з b в a. Компонента сильної зв'язності орієнтованого графа G — це найбільший сильно зв'язаний підграф. Якщо кожну компонента сильної зв'язності стягнути до однієї вершини, отримаємо орієнтований ациклічний граф, ущільнення (англ. condensation) G. Орієнтований граф є ациклічним тоді і лише тоді, коли він не має компонент сильної зв'язності з більш як однією вершиною, бо орієнтований цикл є сильно зв'язним і кожна нетривіальна компонента сильної зв'язності містить щонайменше один орієнтований цикл. (uk)
|
| rdfs:label
|
- مخطط قوي التوصيل (ar)
- Component fortament connex (ca)
- Silně souvislá komponenta (cs)
- Componente fuertemente conexo (es)
- Composante fortement connexe (fr)
- Componente fortemente connessa (it)
- 강한 연결 요소 (ko)
- Składowa silnie spójna (pl)
- Strongly connected component (en)
- Компонента сильной связности (ru)
- Компонента сильної зв'язності графа (uk)
- 强连通分量 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
