Component (graph theory) (original) (raw)
Komponenta grafu (Komponenta souvislosti) je maximální souvislý podgraf, t.j. v tomto podgrafu najdeme cestu z vrcholu do vrcholu pro jakékoliv vrcholy v podgrafu. Jsou to všechny indukované podgrafy na jednotlivých třídách ekvivalence souvislosti. Je to souvislý podgraf, který není obsažen v žádném větším souvislém podgrafu. Souvislý graf má právě jednu komponentu. Z algoritmického hlediska je určení komponent a testování souvislosti grafu snadným problémem. K oběma problémům lze použít například algoritmus prohledávání do hloubky.
| Property | Value |
|---|---|
| dbo:abstract | Komponenta grafu (Komponenta souvislosti) je maximální souvislý podgraf, t.j. v tomto podgrafu najdeme cestu z vrcholu do vrcholu pro jakékoliv vrcholy v podgrafu. Jsou to všechny indukované podgrafy na jednotlivých třídách ekvivalence souvislosti. Je to souvislý podgraf, který není obsažen v žádném větším souvislém podgrafu. Souvislý graf má právě jednu komponentu. Z algoritmického hlediska je určení komponent a testování souvislosti grafu snadným problémem. K oběma problémům lze použít například algoritmus prohledávání do hloubky. (cs) In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices. In random graphs, a frequently occurring phenomenon is the incidence of a giant component, one component that is significantly larger than the others; and of a percolation threshold, an edge probability above which a giant component exists and below which it does not. The components of a graph can be constructed in linear time, and a special case of the problem, connected-component labeling, is a basic technique in image analysis. Dynamic connectivity algorithms maintain components as edges are inserted or deleted in a graph, in low time per change. In computational complexity theory, connected components have been used to study algorithms with limited space complexity, and sublinear time algorithms can accurately estimate the number of components. (en) En teoría de grafos, un componente o componente conexo es un subgrafo inducido de un grafo en que cualesquiera dos vértices están conectados mediante un camino. Un vértice aislado, el grafo trivial o un grafo conexo son en sí mismos componentes. Para los grafos no dirigidos, se habla sencillamente de componentes o componentes conexos. Sin embargo, para grafos dirigidos, se habla de componente débilmente conexo, si no se considera el sentido de las aristas, o bien de componente fuertemente conexo, cuando sí se considera el sentido de las aristas. (es) Nella teoria dei grafi, una componente connessa (o semplicemente una componente) di un grafo indiretto è un sottografo in cui: * qualsiasi coppia di vertici è connessa da cammini * il sottografo non è connesso a nessun vertice addizionale del supergrafo. Ad esempio, il grafo mostrato nell'illustrazione sulla destra ha tre componenti connesse. Un grafo che è esso stesso connesso ha esattamente una componente connessa, che consiste nell'intero grafo. (it) Spójna składowa grafu nieskierowanego G – spójny podgraf grafu G nie zawarty w większym podgrafie spójnym grafu G. Innymi słowy spójna składowa grafu jest to taki podgraf, który można ‘wydzielić’ z całego grafu bez usuwania krawędzi. Graf spójny ma jedną spójna składową. Dla przykładu, w lesie spójnymi składowymi są drzewa. (pl) Компонента связности графа (или просто компонента графа ) — максимальный (по включению) связный подграф графа . Другими словами, это подграф , порождённый множеством вершин, в котором для любой пары вершин в графе существует -цепь и для любой пары вершин , не существует -цепи. Для ориентированных графов определено понятие компоненты сильной связности. (ru) En komponent till en graf är en ekvivalensklass till ekvivalensrelationen väg i mellan och . Med andra ord är varje komponent en isolerad grupp av sammanlänkade noder. De är sammanlänkade på så sätt att varje nod har en väg till de resterande noderna. Denna artikel om kombinatorik eller diskret matematik saknar väsentlig information. Du kan hjälpa till genom att lägga till den. (sv) 在圖論中，元件又稱為連通元件、元件、或分支，是一個無向子圖，在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點，且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖，也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。 如果圖是一個有向圖，而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件；而若圖上任兩個點之間皆有不止一條路徑連通，則稱為。 (zh) В теорії графів, компонента зв'язності неорієнтованого графа це , в якому будь-які дві вершини зв'язані одна з одною шляхами, і вони не зв'язані з ніякими додатковими вершинами. Наприклад, граф на малюнку праворуч має три компоненти зв'язності. Зв'язний граф має рівно одну компоненту зв'язності, яка містить весь граф. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Pseudoforest.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.mathworks.com/matlabcentral/fileexchange/42040-find-network-components http://www.cs.sunysb.edu/~algorith/files/dfs-bfs.shtml |
| dbo:wikiPageID | 246223 (xsd:integer) |
| dbo:wikiPageLength | 27545 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1075419024 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Memory_access_pattern dbr:Biconnected_component dbr:Algebraic_graph_theory dbc:Graph_connectivity dbr:Betti_number dbr:Percolation_theory dbr:Perfect_matching dbr:Undirected_graph dbr:Decision_problem dbr:Depth-first_search dbr:Dynamic_connectivity dbr:Induced_subgraph dbr:Topological_invariant dbr:Pseudoforest dbr:Isolated_vertex dbr:Weak_component dbc:Graph_theory_objects dbr:Connected_component_(topology) dbr:Connected_graph dbr:Connectivity_(graph_theory) dbr:Matrix_(mathematics) dbr:SL_(complexity) dbr:General_position dbr:Chromatic_polynomial dbr:Cluster_graph dbr:Eigenvalue dbr:Glossary_of_graph_theory dbr:Connected-component_labeling dbr:Equivalence_class dbr:Erdős–Rényi_model dbr:L_(complexity) dbr:Linear_time dbr:Logarithm dbr:Complexity_class dbr:Computational_complexity_theory dbr:Kruskal's_algorithm dbr:Path_(graph_theory) dbr:Matroid dbr:Matroid_rank dbr:Transitive_closure dbr:Transitive_relation dbr:Tree_(graph_theory) dbr:Tutte_theorem dbr:Walk_(graph_theory) dbr:Disjoint_sets dbr:Disjoint_union_of_graphs dbr:Dual_matroid dbr:Laplacian_matrix dbr:Moore_neighborhood dbr:Adjacency_list dbr:Amortized_analysis dbr:Equivalence_relation dbr:Euclidean_space dbr:Breadth-first_search dbr:Directed_graph dbr:Graph_theory dbr:Graph_toughness dbr:Graphic_matroid dbr:Pixel_connectivity dbr:Strongly_connected_component dbr:Random_variable dbr:Rank_(graph_theory) dbr:Reachability dbr:Reduction_(complexity) dbr:Coupon_collector's_problem dbr:Ackermann_function dbr:Symmetric_relation dbr:Percolation_threshold dbr:Tutte–Berge_formula dbr:Disjoint-set_data_structure dbr:Pixel dbr:Circuit_rank dbr:Graph_invariant dbr:Empty_graph dbr:Maximum_matching dbr:Minimum_spanning_tree dbr:Reflexive_relation dbr:Turing_machine dbr:Von_Neumann_neighborhood dbr:With_high_probability dbr:Image_analysis dbr:Forest_(graph_theory) dbr:Spanning_forest dbr:Giant_component dbr:Maximal_clique dbr:Topological_space dbr:Topological_graph_theory dbr:Random_graph dbr:Space_complexity dbr:Disjoint_set dbr:Absolute_error dbr:Expected_time dbr:Sublinear_time dbr:File:Equivalentie.svg dbr:File:Pseudoforest.svg dbr:File:Critical_1000-vertex_Erdős–Rényi–Gilbert_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Good_article dbt:Harvtxt dbt:Main dbt:R dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_connectivity dbc:Graph_theory_objects |
| rdfs:comment | Komponenta grafu (Komponenta souvislosti) je maximální souvislý podgraf, t.j. v tomto podgrafu najdeme cestu z vrcholu do vrcholu pro jakékoliv vrcholy v podgrafu. Jsou to všechny indukované podgrafy na jednotlivých třídách ekvivalence souvislosti. Je to souvislý podgraf, který není obsažen v žádném větším souvislém podgrafu. Souvislý graf má právě jednu komponentu. Z algoritmického hlediska je určení komponent a testování souvislosti grafu snadným problémem. K oběma problémům lze použít například algoritmus prohledávání do hloubky. (cs) En teoría de grafos, un componente o componente conexo es un subgrafo inducido de un grafo en que cualesquiera dos vértices están conectados mediante un camino. Un vértice aislado, el grafo trivial o un grafo conexo son en sí mismos componentes. Para los grafos no dirigidos, se habla sencillamente de componentes o componentes conexos. Sin embargo, para grafos dirigidos, se habla de componente débilmente conexo, si no se considera el sentido de las aristas, o bien de componente fuertemente conexo, cuando sí se considera el sentido de las aristas. (es) Nella teoria dei grafi, una componente connessa (o semplicemente una componente) di un grafo indiretto è un sottografo in cui: * qualsiasi coppia di vertici è connessa da cammini * il sottografo non è connesso a nessun vertice addizionale del supergrafo. Ad esempio, il grafo mostrato nell'illustrazione sulla destra ha tre componenti connesse. Un grafo che è esso stesso connesso ha esattamente una componente connessa, che consiste nell'intero grafo. (it) Spójna składowa grafu nieskierowanego G – spójny podgraf grafu G nie zawarty w większym podgrafie spójnym grafu G. Innymi słowy spójna składowa grafu jest to taki podgraf, który można ‘wydzielić’ z całego grafu bez usuwania krawędzi. Graf spójny ma jedną spójna składową. Dla przykładu, w lesie spójnymi składowymi są drzewa. (pl) Компонента связности графа (или просто компонента графа ) — максимальный (по включению) связный подграф графа . Другими словами, это подграф , порождённый множеством вершин, в котором для любой пары вершин в графе существует -цепь и для любой пары вершин , не существует -цепи. Для ориентированных графов определено понятие компоненты сильной связности. (ru) En komponent till en graf är en ekvivalensklass till ekvivalensrelationen väg i mellan och . Med andra ord är varje komponent en isolerad grupp av sammanlänkade noder. De är sammanlänkade på så sätt att varje nod har en väg till de resterande noderna. Denna artikel om kombinatorik eller diskret matematik saknar väsentlig information. Du kan hjälpa till genom att lägga till den. (sv) 在圖論中，元件又稱為連通元件、元件、或分支，是一個無向子圖，在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點，且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖，也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。 如果圖是一個有向圖，而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件；而若圖上任兩個點之間皆有不止一條路徑連通，則稱為。 (zh) В теорії графів, компонента зв'язності неорієнтованого графа це , в якому будь-які дві вершини зв'язані одна з одною шляхами, і вони не зв'язані з ніякими додатковими вершинами. Наприклад, граф на малюнку праворуч має три компоненти зв'язності. Зв'язний граф має рівно одну компоненту зв'язності, яка містить весь граф. (uk) In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. (en) |
| rdfs:label | Komponenta grafu (cs) Component (graph theory) (en) Componente (teoría de grafos) (es) Componente connessa (teoria dei grafi) (it) 연결 요소 (그래프 이론) (ko) Spójna składowa grafu (pl) Компонента связности графа (ru) Komponent (grafteori) (sv) Компонента зв'язності графа (uk) 元件 (圖論) (zh) |
| owl:sameAs | wikidata:Component (graph theory) dbpedia-cs:Component (graph theory) dbpedia-cy:Component (graph theory) dbpedia-es:Component (graph theory) dbpedia-fa:Component (graph theory) dbpedia-hu:Component (graph theory) dbpedia-it:Component (graph theory) dbpedia-ko:Component (graph theory) dbpedia-lmo:Component (graph theory) dbpedia-pl:Component (graph theory) dbpedia-ro:Component (graph theory) dbpedia-ru:Component (graph theory) dbpedia-sk:Component (graph theory) dbpedia-sr:Component (graph theory) dbpedia-sv:Component (graph theory) http://ta.dbpedia.org/resource/கூறு_(கோட்டுருவியல்) dbpedia-uk:Component (graph theory) dbpedia-vi:Component (graph theory) dbpedia-zh:Component (graph theory) https://global.dbpedia.org/id/2n4Cr |
| prov:wasDerivedFrom | wikipedia-en:Component_(graph_theory)?oldid=1075419024&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Critical_1000-vertex_Erdős–Rényi–Gilbert_graph.svg wiki-commons:Special:FilePath/Equivalentie.svg wiki-commons:Special:FilePath/Pseudoforest.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Component_(graph_theory) |
| is dbo:wikiPageRedirects of | dbr:Connected_component_(graph_theory) dbr:Component_graph |
| is dbo:wikiPageWikiLink of | dbr:Prime_graph dbr:Defective_coloring dbr:Interlocking_directorate dbr:Weak_component dbr:Cactus_graph dbr:Calculus_on_finite_weighted_graphs dbr:Feedback_vertex_set dbr:Harmonic_series_(mathematics) dbr:Transitive_closure dbr:Tutte_theorem dbr:Expander_graph dbr:Balance_theory dbr:Graph_homology dbr:Handshaking_lemma dbr:Counting_on_Frameworks dbr:Hyperbola dbr:Homological_connectivity dbr:Borůvka's_algorithm dbr:Connected_component_(graph_theory) dbr:Grid_bracing dbr:Kirchhoff's_theorem dbr:Maria_Silvia_Lucido dbr:Universal_vertex dbr:Sachs_subgraph dbr:Component_graph |
| is foaf:primaryTopic of | wikipedia-en:Component_(graph_theory) |
