Path (graph theory)
http://dbpedia.org/resource/Path_(graph_theory) an entity of type: Thing
V teorii grafů se termínem cesta v grafu G = (V, E) označuje posloupnost , pro kterou platí (případně pro orientované grafy) a navíc . Je to tedy posloupnost vrcholů, pro kterou platí, že v grafu existuje hrana z daného vrcholu do jeho následníka. Žádné dva vrcholy (a tedy ani hrany) se přitom neopakují. Poslední podmínka odlišuje cestu od dvou podobných pojmů:
* tah je posloupnost, kde se mohou opakovat vrcholy, ale ne hrany
* sled je posloupnost, kde se mohou opakovat i hrany
rdf:langString
In der Graphentheorie wird eine Folge von Knoten, in welcher jeweils zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind, als Weg (manchmal auch als Pfad) bezeichnet. Eine Folge von Kanten, in welcher jeweils zwei aufeinanderfolgende Kanten einen gemeinsamen Knoten haben, wird als Kantenzug (manchmal auch als Kantenfolge) bezeichnet.
rdf:langString
Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin.
rdf:langString
グラフ理論において、グラフの道（みち）またはパス（英: path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al. (1990) では、道に関するより進んだアルゴリズム的項目を網羅している。
rdf:langString
그래프 이론에서 경로(經路, 영어: path 패스[*])는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이다. 유향 그래프에서 유향 경로 또는 방향 경로, 디패스(dipath, 다이패스)는 간선이 모두 같은 방향을 향하는 제약이 있는, 일련의 꼭짓점을 연결하는 일련의 간선들이다. 단순 경로는 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로를 말한다.
rdf:langString
在图论中，一个图中一条道路（path）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。 道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (1985) 或 Diestel (2005)、Korte et al. (1990) 包含了图中关于道路的更高等算法论题。
rdf:langString
En teoria de grafs, un camí o ruta és una seqüència de vèrtexs dins d'un graf tal que hi ha una aresta entre cada vèrtex i el següent. Es diu que dos vèrtexs estan connectats si existeix un camí que va d'un a un altre, en cas contrari estaran desconnectats. Dos vèrtexs poden estar connectats per diversos camins. El nombre d'arestes dins d'un camí és la seva longitud. Així, els vèrtexs adjacents estan connectats per un camí de longitud 1, i els segons veïns per un camí de longitud 2. Si un camí comença i acaba en el mateix vèrtex s'anomena cicle.
rdf:langString
En teoría de grafos, un camino (en inglés, walk, y en ocasiones traducido también como recorrido) es una sucesión de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es incidente con las aristas que le siguen y le preceden en la secuencia. Dos vértices están conectados o son accesibles si existe un camino que forma una trayectoria para llegar de uno al otro; en caso contrario, los vértices están desconectados o bien son inaccesibles.
rdf:langString
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.
rdf:langString
Em teoria dos grafos, um caminho em um grafo é uma sequência finita ou infinita de vértices conectados por uma sequência de arestas que, na maioria das definições, são todos diferentes uns dos outros. O primeiro vértice é chamado de vértice inicial e o último é chamado de vértice final. Em um grafo direcionado, um caminho dirigido (às vezes chamado de dipath) é uma sequência de arestas que se conectam a uma sequência de vértices, mas com a restrição de que as arestas sejam todas dirigidas no mesmo sentido.
rdf:langString
Ścieżka – ścieżką łączącą z o długości n nazywa się ciąg wierzchołków taki, że dla każdego istnieje krawędź z do (w przypadku grafu nieskierowanego możemy mówić, że sąsiadują z sobą). Często przez ścieżkę rozumiemy również dodatkowo ciąg (czasami zbiór) krawędzi łączących kolejne wierzchołki w ciągu wierzchołków ścieżki. Ciąg tych krawędzi posiada zawsze wyrazów, stąd określenie "długość", co jest najbardziej widoczne w przypadku szczególnego przypadku ścieżek bez powtarzających się wierzchołków (tzw. dróg). Ścieżka prosta – ścieżka, w której nie ma powtarzających się wierzchołków.
rdf:langString
Шля́х (в теорії графів) — ланцюг, всі ребра якого орієнтовані в напряму руху від початкової до кінцевої вершини ланцюга. Шлях позначають символом μ(x0, xl) = (u1, u2, …, ul), де дуга ui вершинам xi-1 та xi.Шлях, в якому будь-яка вершина не зустрічається двічі, називається елементарним. Якщо xi та xj — деякі вершини графу, для яких існує шлях μ(xi, xj) то вершина xj досяжна із вершини xi, а вершина xi — зворотно досяжна із вершини xj. Множина всіх досяжних із xi вершин позначається символом D(xi), а зворотно досяжних — D−1(xi). Для будь-якої множини A вершин визначається досяжна множина .
rdf:langString
rdf:langString
Camí (teoria de grafs)
rdf:langString
Cesta (graf)
rdf:langString
Weg (Graphentheorie)
rdf:langString
Camino (teoría de grafos)
rdf:langString
Chaîne (théorie des graphes)
rdf:langString
경로 (그래프 이론)
rdf:langString
道 (グラフ理論)
rdf:langString
Path (graph theory)
rdf:langString
Ścieżka (teoria grafów)
rdf:langString
Caminho (teoria dos grafos)
rdf:langString
道路 (图论)
rdf:langString
Шлях (теорія графів)
xsd:integer
638889
xsd:integer
1124188559
rdf:langString
V teorii grafů se termínem cesta v grafu G = (V, E) označuje posloupnost , pro kterou platí (případně pro orientované grafy) a navíc . Je to tedy posloupnost vrcholů, pro kterou platí, že v grafu existuje hrana z daného vrcholu do jeho následníka. Žádné dva vrcholy (a tedy ani hrany) se přitom neopakují. Poslední podmínka odlišuje cestu od dvou podobných pojmů:
* tah je posloupnost, kde se mohou opakovat vrcholy, ale ne hrany
* sled je posloupnost, kde se mohou opakovat i hrany
rdf:langString
En teoria de grafs, un camí o ruta és una seqüència de vèrtexs dins d'un graf tal que hi ha una aresta entre cada vèrtex i el següent. Es diu que dos vèrtexs estan connectats si existeix un camí que va d'un a un altre, en cas contrari estaran desconnectats. Dos vèrtexs poden estar connectats per diversos camins. El nombre d'arestes dins d'un camí és la seva longitud. Així, els vèrtexs adjacents estan connectats per un camí de longitud 1, i els segons veïns per un camí de longitud 2. Si un camí comença i acaba en el mateix vèrtex s'anomena cicle. Formalment, un camí és un graf amb vèrtexs i arestes . La longitud del camí és el nombre d'arestes, .
rdf:langString
In der Graphentheorie wird eine Folge von Knoten, in welcher jeweils zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind, als Weg (manchmal auch als Pfad) bezeichnet. Eine Folge von Kanten, in welcher jeweils zwei aufeinanderfolgende Kanten einen gemeinsamen Knoten haben, wird als Kantenzug (manchmal auch als Kantenfolge) bezeichnet.
rdf:langString
En teoría de grafos, un camino (en inglés, walk, y en ocasiones traducido también como recorrido) es una sucesión de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es incidente con las aristas que le siguen y le preceden en la secuencia. Dos vértices están conectados o son accesibles si existe un camino que forma una trayectoria para llegar de uno al otro; en caso contrario, los vértices están desconectados o bien son inaccesibles. Dos vértices pueden estar conectados por varios caminos. La longitud de un camino es su número de aristas. Así, en un grafo no dirigido, los vértices adyacentes están conectados por un camino de longitud 1, los segundos vecinos por un camino de longitud 2, y así sucesivamente. Un grafo no dirigido es conexo si todos sus vértices están conectados a través de un camino. Un grafo conexo cuyos vértices y aristas permiten definir un camino es un grafo camino.
rdf:langString
Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin.
rdf:langString
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs.
rdf:langString
グラフ理論において、グラフの道（みち）またはパス（英: path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al. (1990) では、道に関するより進んだアルゴリズム的項目を網羅している。
rdf:langString
그래프 이론에서 경로(經路, 영어: path 패스[*])는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이다. 유향 그래프에서 유향 경로 또는 방향 경로, 디패스(dipath, 다이패스)는 간선이 모두 같은 방향을 향하는 제약이 있는, 일련의 꼭짓점을 연결하는 일련의 간선들이다. 단순 경로는 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로를 말한다.
rdf:langString
Ścieżka – ścieżką łączącą z o długości n nazywa się ciąg wierzchołków taki, że dla każdego istnieje krawędź z do (w przypadku grafu nieskierowanego możemy mówić, że sąsiadują z sobą). Często przez ścieżkę rozumiemy również dodatkowo ciąg (czasami zbiór) krawędzi łączących kolejne wierzchołki w ciągu wierzchołków ścieżki. Ciąg tych krawędzi posiada zawsze wyrazów, stąd określenie "długość", co jest najbardziej widoczne w przypadku szczególnego przypadku ścieżek bez powtarzających się wierzchołków (tzw. dróg). Ścieżka prosta – ścieżka, w której nie ma powtarzających się wierzchołków. W przypadku grafu (krawędzi) ważonych, należy odróżnić pojęcie długości od odległości (to jest sumy wag krawędzi łączących kolejne wierzchołki w ścieżce - być może liczone wielokrotnie). Ścieżki są ważnym elementem teorii grafów oraz wielu algorytmów.
rdf:langString
Em teoria dos grafos, um caminho em um grafo é uma sequência finita ou infinita de vértices conectados por uma sequência de arestas que, na maioria das definições, são todos diferentes uns dos outros. O primeiro vértice é chamado de vértice inicial e o último é chamado de vértice final. Em um grafo direcionado, um caminho dirigido (às vezes chamado de dipath) é uma sequência de arestas que se conectam a uma sequência de vértices, mas com a restrição de que as arestas sejam todas dirigidas no mesmo sentido. Os caminhos são conceitos fundamentais de teoria de grafos, descrito nas seções introdutórias da maioria dos textos sobre teoria dos grafos.
rdf:langString
在图论中，一个图中一条道路（path）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。 道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (1985) 或 Diestel (2005)、Korte et al. (1990) 包含了图中关于道路的更高等算法论题。
rdf:langString
Шля́х (в теорії графів) — ланцюг, всі ребра якого орієнтовані в напряму руху від початкової до кінцевої вершини ланцюга. Шлях позначають символом μ(x0, xl) = (u1, u2, …, ul), де дуга ui вершинам xi-1 та xi.Шлях, в якому будь-яка вершина не зустрічається двічі, називається елементарним. Якщо xi та xj — деякі вершини графу, для яких існує шлях μ(xi, xj) то вершина xj досяжна із вершини xi, а вершина xi — зворотно досяжна із вершини xj. Множина всіх досяжних із xi вершин позначається символом D(xi), а зворотно досяжних — D−1(xi). Для будь-якої множини A вершин визначається досяжна множина . Аналогічно визначається зворотно досяжна множина D−1(A). Шлях, що містить всі дуги орієнтованого графу, називається ейлеровим.
xsd:nonNegativeInteger
9676
