| 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 16108 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
