Strongly connected component (original) (raw)
يقال أن مخططاً موجهاً ما قوي التوصيل (بالإنجليزية: strongly connected)، إذا وجد مسلك أو طريق من كل عقدة في المخطط يوصل إلى أي نقطة أخرى. وإذا فسرنا ذلك من ناحية الرياضيات فإن هذه الخاصية تترجم بأن المصفوفة التابعة لهذا المخطط تكون غير قابلة للاختزال أي (irreducible) أي أن أي قوة للمصفوفة تعطي مصفوفة ليست صفرا.
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/Scc-1.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/ http://code.google.com/p/jbpt/ |
| dbo:wikiPageID | 684680 (xsd:integer) |
| dbo:wikiPageLength | 12870 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116542639 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Robert_Tarjan dbr:Binary_relation dbc:Graph_connectivity dbr:Perfect_matching dbr:Depth-first_search dbr:Dulmage–Mendelsohn_decomposition dbr:Ear_decomposition dbr:Induced_subgraph dbr:Weak_component dbr:Connectivity_(graph_theory) dbr:Equivalence_class dbr:Linear_time dbr:Stack_(abstract_data_type) dbr:Clique_(graph_theory) dbr:Path_(graph_theory) dbc:Directed_graphs dbr:Transpose_graph dbr:K-edge-connected_graph dbr:Analysis_of_parallel_algorithms dbr:Edsger_W._Dijkstra dbr:Equivalence_relation dbr:Breadth-first_search dbr:Partition_of_a_set dbr:Directed_graph dbr:Reachability dbr:2-satisfiability dbr:Bipartite_graph dbr:Modular_decomposition dbr:Tarjan's_strongly_connected_components_algorithm dbr:Directed_acyclic_graph dbr:Divide_and_conquer_algorithm dbr:Connected_component_(graph_theory) dbr:Graph_orientation dbr:Kosaraju's_algorithm dbr:Micha_Sharir dbr:Maximal_element dbr:Implication_graph dbr:S._Rao_Kosaraju dbr:Path-based_strong_component_algorithm dbr:Robbins'_theorem dbr:Strong_connectivity_augmentation dbr:Vertex_contraction dbr:File:Scc-1.svg dbr:File:Graph_Condensation.svg |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist dbt:Short_description dbt:Graph_connectivity_sidebar |
| dcterms:subject | dbc:Graph_connectivity dbc:Directed_graphs |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Graph107000195 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:VisualCommunication106873252 yago:WikicatDirectedGraphs |
| 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 | freebase:Strongly connected component yago-res:Strongly connected component wikidata:Strongly connected component dbpedia-ar:Strongly connected component dbpedia-ca:Strongly connected component dbpedia-cs:Strongly connected component dbpedia-es:Strongly connected component dbpedia-fa:Strongly connected component dbpedia-fr:Strongly connected component dbpedia-he:Strongly connected component dbpedia-hu:Strongly connected component http://hy.dbpedia.org/resource/Ամուր_կապակցված_բաղադրիչներ dbpedia-it:Strongly connected component dbpedia-ko:Strongly connected component dbpedia-pl:Strongly connected component dbpedia-ru:Strongly connected component dbpedia-sr:Strongly connected component dbpedia-th:Strongly connected component dbpedia-uk:Strongly connected component dbpedia-vi:Strongly connected component dbpedia-zh:Strongly connected component https://global.dbpedia.org/id/ugUM |
| prov:wasDerivedFrom | wikipedia-en:Strongly_connected_component?oldid=1116542639&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Scc-1.svg wiki-commons:Special:FilePath/Graph_Condensation.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Strongly_connected_component |
| is dbo:wikiPageDisambiguates of | dbr:SCC dbr:Component |
| is dbo:wikiPageRedirects of | dbr:Condensation_(graph) dbr:Condensation_(graph_theory) dbr:Diconnected_component dbr:SCC_(graph_theory) dbr:Strongly-connected_component dbr:Strongly-connected_components dbr:Strongly_Connected_Components dbr:Strongly_connected dbr:Strongly_connected_components dbr:Strongly_connected_graph |
| is dbo:wikiPageWikiLink of | dbr:Quantum_complexity_theory dbr:Entanglement_(graph_measure) dbr:Parity_game dbr:Deterministic_finite_automaton dbr:Aperiodic_graph dbr:List_of_graph_theory_topics dbr:Reversible_cellular_automaton dbr:Cycle_(graph_theory) dbr:Dulmage–Mendelsohn_decomposition dbr:SP-DEVS dbr:Weak_component dbr:Condensation_(graph) dbr:Condensation_(graph_theory) dbr:Connectivity_(graph_theory) dbr:Quotient_graph dbr:Glossary_of_graph_theory dbr:Connectedness dbr:Skew-symmetric_graph dbr:Closeness_centrality dbr:Closure_problem dbr:Component_(graph_theory) dbr:Feedback_arc_set dbr:Top_trading_cycle dbr:Maximally-matchable_edge dbr:Büchi_automaton dbr:Topology_of_the_World_Wide_Web dbr:Tournament_(graph_theory) dbr:Transitive_closure dbr:Transpose_graph dbr:Least_fixed_point dbr:Link_farm dbr:Transitive_reduction dbr:Eulerian_path dbr:Null_graph dbr:Fair_computational_tree_logic dbr:Perron–Frobenius_theorem dbr:2-satisfiability dbr:Hamiltonian_path dbr:Edge_contraction dbr:Tarjan's_strongly_connected_components_algorithm dbr:Diconnected_component dbr:Directed_acyclic_graph dbr:Green's_relations dbr:Grid_bracing dbr:Ilona_Palásti dbr:Kosaraju's_algorithm dbr:Ore's_theorem dbr:Mixed_Chinese_postman_problem dbr:SCC dbr:Component dbr:Implication_graph dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Path-based_strong_component_algorithm dbr:Finite_&_Deterministic_Discrete_Event_System_Specification dbr:Weak_Büchi_automaton dbr:Small-world_experiment dbr:True_quantified_Boolean_formula dbr:Road_coloring_theorem dbr:Strong_connectivity_augmentation dbr:SCC_(graph_theory) dbr:Strongly-connected_component dbr:Strongly-connected_components dbr:Strongly_Connected_Components dbr:Strongly_connected dbr:Strongly_connected_components dbr:Strongly_connected_graph |
| is foaf:primaryTopic of | wikipedia-en:Strongly_connected_component |
