Reachability (original) (raw)
그래프 이론에서 도달성, 도달 가능성(reachability)은 그래프 안의 하나의 꼭짓점에서 다른 꼭짓점으로 도달할 수 있는 가능성을 말한다. 로 시작하고 로 끝나는 인접한 일련의 꼭짓점(예: 경로)이 있다면 꼭짓점 는 꼭짓점 에 도달할 수 있다.(그리고 는 로부터 도달이 가능하다) 방향이 없는(무향) 그래프에서 한 쌍의 꼭짓점 간의 도달성은 그래프의 연결 요소를 식별함으로써 결정할 수 있다. 이러한 그래프에서 임의의 쌍의 꼭짓점들은 동일한 연결 요소에 속해 있을 경우 서로에게 도달할 수 있다. 무향 그래프의 연결 요소는 선형 시간에서 식별이 가능하다.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex can reach a vertex (and is reachable from ) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with and ends with . In an undirected graph, reachability between all pairs of vertices can be determined by identifying the connected components of the graph. Any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component; therefore, in such a graph, reachability is symmetric ( reaches iff reaches ). The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a directed graph (which, incidentally, need not be symmetric). (en) 그래프 이론에서 도달성, 도달 가능성(reachability)은 그래프 안의 하나의 꼭짓점에서 다른 꼭짓점으로 도달할 수 있는 가능성을 말한다. 로 시작하고 로 끝나는 인접한 일련의 꼭짓점(예: 경로)이 있다면 꼭짓점 는 꼭짓점 에 도달할 수 있다.(그리고 는 로부터 도달이 가능하다) 방향이 없는(무향) 그래프에서 한 쌍의 꼭짓점 간의 도달성은 그래프의 연결 요소를 식별함으로써 결정할 수 있다. 이러한 그래프에서 임의의 쌍의 꼭짓점들은 동일한 연결 요소에 속해 있을 경우 서로에게 도달할 수 있다. 무향 그래프의 연결 요소는 선형 시간에서 식별이 가능하다. (ko) Osiągalność (teoria grafów) – relacja dwuargumentowa określona na zbiorze wierzchołków danego grafu skierowanego G = (V, E), gdzie V jest skończonym zbiorem wierzchołków i E jest skończonym zbiorem krawędzi (które są parami wierzchołków) tego grafu. Relacja osiągalności zachodzi dla pary (x,y) (x,y ∊ V) wtedy i tylko wtedy, gdy istnieje ścieżka w grafie G prowadząca od wierzchołka x do wierzchołka y. Wówczas mówimy, że wierzchołek y jest osiągalny z wierzchołka x w grafie G. (pl) Em teoria dos grafos, a atingibilidade se refere a capacidade de ir de um vértice para outro em um grafo. Dizemos que um vértice pode alcançar outro vértice (ou que é atingível a partir de ) se exite uma sequência de vértices adjacentes (ex.: um caminho) que começam com e terminam com . Em um grafo não-direcionado, é suficiente identificar apenas os componentes conexos, assim como qualquer par de vértices, em tal grafo, pode se alcançar se e somente se eles pertencem ao mesmo componente conexo. Os componentes conexos de um grafo podem ser identificados em tempo linear. Lembramos que este artigo foca em atingibilidade nas configurações de grafos orientados. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Graph_suitable_for_Kameda's_method.svg?width=300 |
| dbo:wikiPageID | 2833097 (xsd:integer) |
| dbo:wikiPageLength | 16108 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1111929893 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preorder dbc:Graph_connectivity dbr:Relation_(mathematics) dbr:Cycle_(graph_theory) dbr:Glossary_of_graph_theory dbr:Planar_Graph dbr:Planar_Separator_Theorem dbr:Linear_time dbr:Path_(graph_theory) dbr:Transitive_closure dbr:Data_pre-processing dbr:Gammoid dbr:Garbage_collection_(computer_science) dbr:Transitive_reduction dbr:Directed_graph dbr:Floyd–Warshall_algorithm dbr:Graph_theory dbr:Iterative_deepening_depth-first_search dbr:Directed_acyclic_graph dbr:Planar_graph dbr:St-connectivity dbr:Connected_component_(graph_theory) dbr:Iff dbr:Mikkel_Thorup dbr:Vertex_(graph_theory) dbr:Partial_order dbr:Breadth_first_search dbr:File:Graph_suitable_for_Kameda's_method.svg dbr:File:Kameda's_algorithm_run.svg |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_connectivity |
| rdfs:comment | 그래프 이론에서 도달성, 도달 가능성(reachability)은 그래프 안의 하나의 꼭짓점에서 다른 꼭짓점으로 도달할 수 있는 가능성을 말한다. 로 시작하고 로 끝나는 인접한 일련의 꼭짓점(예: 경로)이 있다면 꼭짓점 는 꼭짓점 에 도달할 수 있다.(그리고 는 로부터 도달이 가능하다) 방향이 없는(무향) 그래프에서 한 쌍의 꼭짓점 간의 도달성은 그래프의 연결 요소를 식별함으로써 결정할 수 있다. 이러한 그래프에서 임의의 쌍의 꼭짓점들은 동일한 연결 요소에 속해 있을 경우 서로에게 도달할 수 있다. 무향 그래프의 연결 요소는 선형 시간에서 식별이 가능하다. (ko) Osiągalność (teoria grafów) – relacja dwuargumentowa określona na zbiorze wierzchołków danego grafu skierowanego G = (V, E), gdzie V jest skończonym zbiorem wierzchołków i E jest skończonym zbiorem krawędzi (które są parami wierzchołków) tego grafu. Relacja osiągalności zachodzi dla pary (x,y) (x,y ∊ V) wtedy i tylko wtedy, gdy istnieje ścieżka w grafie G prowadząca od wierzchołka x do wierzchołka y. Wówczas mówimy, że wierzchołek y jest osiągalny z wierzchołka x w grafie G. (pl) In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex can reach a vertex (and is reachable from ) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with and ends with . (en) Em teoria dos grafos, a atingibilidade se refere a capacidade de ir de um vértice para outro em um grafo. Dizemos que um vértice pode alcançar outro vértice (ou que é atingível a partir de ) se exite uma sequência de vértices adjacentes (ex.: um caminho) que começam com e terminam com . (pt) |
| rdfs:label | 도달성 (ko) Reachability (en) Osiągalność (teoria grafów) (pl) Atingibilidade (teoria dos grafos) (pt) Достижимость (ru) |
| owl:sameAs | freebase:Reachability wikidata:Reachability dbpedia-hu:Reachability dbpedia-ko:Reachability dbpedia-pl:Reachability dbpedia-pt:Reachability dbpedia-ru:Reachability https://global.dbpedia.org/id/MuFG |
| prov:wasDerivedFrom | wikipedia-en:Reachability?oldid=1111929893&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Graph_suitable_for_Kameda's_method.svg wiki-commons:Special:FilePath/Kameda's_algorithm_run.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Reachability |
| is dbo:wikiPageDisambiguates of | dbr:Reach |
| is dbo:wikiPageRedirects of | dbr:Thorup's_algorithm dbr:Kameda's_algorithm dbr:Graph_reachability dbr:Reachability_matrix dbr:Reachable |
| is dbo:wikiPageWikiLink of | dbr:Preorder dbr:Mirsky's_theorem dbr:Book_embedding dbr:Cycle_detection dbr:Dominance_drawing dbr:JGRASP dbr:Weak_component dbr:Control-flow_graph dbr:Rooted_graph dbr:Upward_planar_drawing dbr:Glossary_of_graph_theory dbr:NL_(complexity) dbr:Configuration_graph dbr:Controlling_for_a_variable dbr:Thorup's_algorithm dbr:L_(complexity) dbr:Argus_–_Audit_Record_Generation_and_Utilization_System dbr:Component_(graph_theory) dbr:P_(complexity) dbr:Matroid_partitioning dbr:Matroid_representation dbr:Topological_sorting dbr:Tournament_(graph_theory) dbr:Transitive_closure dbr:Transitive_reduction dbr:A*_search_algorithm dbr:Partially_ordered_set dbr:Graph_drawing dbr:Strongly_connected_component dbr:Reach dbr:Heartbeat_(computing) dbr:Backbone_network dbr:Hybrid_automaton dbr:Stochastic_Petri_net dbr:Kameda's_algorithm dbr:Coffman–Graham_algorithm dbr:Hierarchical_and_recursive_queries_in_SQL dbr:Reconfiguration dbr:Directed_acyclic_graph dbr:CPAchecker dbr:Polytree dbr:St-connectivity dbr:Graph_reachability dbr:Implicit_graph dbr:Second-order_logic dbr:Series-parallel_partial_order dbr:Maria_(reachability_analyzer) dbr:Underhanded_C_Contest dbr:Multitree dbr:Reachability_matrix dbr:Reachable |
| is foaf:primaryTopic of | wikipedia-en:Reachability |
