Path (graph theory) (original) (raw)
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
| Property | Value |
|---|---|
| dbo:abstract | 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 (cs) 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, . (ca) 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. (de) 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. (es) 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. (fr) 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. (en) グラフ理論において、グラフの道（みち）またはパス（英: path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al. (1990) では、道に関するより進んだアルゴリズム的項目を網羅している。 (ja) 그래프 이론에서 경로(經路, 영어: path 패스[*])는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이다. 유향 그래프에서 유향 경로 또는 방향 경로, 디패스(dipath, 다이패스)는 간선이 모두 같은 방향을 향하는 제약이 있는, 일련의 꼭짓점을 연결하는 일련의 간선들이다. 단순 경로는 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로를 말한다. (ko) Ś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. (pl) 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. (pt) 在图论中，一个图中一条道路（path）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。 道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (1985) 或 Diestel (2005)、Korte et al. (1990) 包含了图中关于道路的更高等算法论题。 (zh) Шля́х (в теорії графів) — ланцюг, всі ребра якого орієнтовані в напряму руху від початкової до кінцевої вершини ланцюга. Шлях позначають символом μ(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). Шлях, що містить всі дуги орієнтованого графу, називається ейлеровим. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Snake-in-the-box_and_Hamiltonian_path.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ https://books.google.com/books%3Fid=vaXv_yhefG8C https://archive.org/details/graphtheorywitha0000bond/page/12 https://archive.org/details/pathsflowsvlsila0000unse |
| dbo:wikiPageID | 638889 (xsd:integer) |
| dbo:wikiPageLength | 9676 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124188559 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:End_(graph_theory) dbr:Bellman–Ford_algorithm dbr:Algorithm dbc:Graph_connectivity dbr:Path_graph dbr:Induced_path dbc:Graph_theory_objects dbr:Connectivity_(graph_theory) dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Shortest_path_problem dbr:Weighted_graph dbr:Edge_(graph_theory) dbr:Directed_graph dbr:Floyd–Warshall_algorithm dbr:Graph_theory dbr:Hamiltonian_path dbr:Dijkstra's_algorithm dbr:Distance_(graph_theory) dbr:Self-avoiding_walk dbr:Sequence dbr:Longest_path_problem dbr:Vertex_(graph_theory) dbr:Shortest-path_graph dbr:Polygonal_chain dbr:Strongly-connected_digraph dbr:File:Snake-in-the-box_and_Hamiltonian_path.svg dbr:File:Trail_but_not_path.svg |
| dbp:wikiPageUsesTemplate | dbt:Interwiki_extra dbt:Authority_control dbt:Cite_book dbt:For dbt:Nowrap_begin dbt:Nowrap_end dbt:Reflist dbt:Sfn dbt:Short_description |
| dct:subject | dbc:Graph_connectivity dbc:Graph_theory_objects |
| gold:hypernym | dbr:Sequence |
| rdf:type | owl:Thing yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| rdfs:comment | 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 (cs) 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. (de) 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. (fr) グラフ理論において、グラフの道（みち）またはパス（英: path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al. (1990) では、道に関するより進んだアルゴリズム的項目を網羅している。 (ja) 그래프 이론에서 경로(經路, 영어: path 패스[*])는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이다. 유향 그래프에서 유향 경로 또는 방향 경로, 디패스(dipath, 다이패스)는 간선이 모두 같은 방향을 향하는 제약이 있는, 일련의 꼭짓점을 연결하는 일련의 간선들이다. 단순 경로는 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로를 말한다. (ko) 在图论中，一个图中一条道路（path）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。 道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (1985) 或 Diestel (2005)、Korte et al. (1990) 包含了图中关于道路的更高等算法论题。 (zh) 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. (ca) 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. (es) 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. (en) 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. (pt) Ś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. (pl) Шля́х (в теорії графів) — ланцюг, всі ребра якого орієнтовані в напряму руху від початкової до кінцевої вершини ланцюга. Шлях позначають символом μ(x0, xl) = (u1, u2, …, ul), де дуга ui вершинам xi-1 та xi.Шлях, в якому будь-яка вершина не зустрічається двічі, називається елементарним. Якщо xi та xj — деякі вершини графу, для яких існує шлях μ(xi, xj) то вершина xj досяжна із вершини xi, а вершина xi — зворотно досяжна із вершини xj. Множина всіх досяжних із xi вершин позначається символом D(xi), а зворотно досяжних — D−1(xi). Для будь-якої множини A вершин визначається досяжна множина . (uk) |
| rdfs:label | Camí (teoria de grafs) (ca) Cesta (graf) (cs) Weg (Graphentheorie) (de) Camino (teoría de grafos) (es) Chaîne (théorie des graphes) (fr) 경로 (그래프 이론) (ko) 道 (グラフ理論) (ja) Path (graph theory) (en) Ścieżka (teoria grafów) (pl) Caminho (teoria dos grafos) (pt) 道路 (图论) (zh) Шлях (теорія графів) (uk) |
| owl:sameAs | freebase:Path (graph theory) yago-res:Path (graph theory) wikidata:Path (graph theory) dbpedia-ca:Path (graph theory) dbpedia-cs:Path (graph theory) dbpedia-de:Path (graph theory) dbpedia-es:Path (graph theory) dbpedia-fa:Path (graph theory) dbpedia-fr:Path (graph theory) dbpedia-he:Path (graph theory) dbpedia-hr:Path (graph theory) dbpedia-ja:Path (graph theory) dbpedia-ko:Path (graph theory) dbpedia-pl:Path (graph theory) dbpedia-pt:Path (graph theory) dbpedia-ro:Path (graph theory) dbpedia-sk:Path (graph theory) http://ta.dbpedia.org/resource/பாதை_(கோட்டுருவியல்) dbpedia-th:Path (graph theory) dbpedia-uk:Path (graph theory) http://ur.dbpedia.org/resource/رستہ_(نظریہ_گراف) dbpedia-vi:Path (graph theory) dbpedia-zh:Path (graph theory) https://global.dbpedia.org/id/RPzj |
| prov:wasDerivedFrom | wikipedia-en:Path_(graph_theory)?oldid=1124188559&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Snake-in-the-box_and_Hamiltonian_path.svg wiki-commons:Special:FilePath/Trail_but_not_path.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Path_(graph_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Path |
| is dbo:wikiPageRedirects of | dbr:Walk_(graph_theory) dbr:Directed_path_(graph_theory) dbr:Dipath dbr:Directed_path dbr:Path_(graph) dbr:Edge_independent_path dbr:Simple_path_(graph_theory) dbr:Vertex_independent_path |
| is dbo:wikiPageWikiLink of | dbr:Preorder dbr:Branch_(disambiguation) dbr:End_(graph_theory) dbr:Enumeration_algorithm dbr:Menger's_theorem dbr:M-separation dbr:Parity_game dbr:Path_coloring dbr:Answer_set_programming dbr:Hypercube_graph dbr:List_of_graph_theory_topics dbr:Path_graph dbr:Petersen's_theorem dbr:Cycle_(graph_theory) dbr:Vertex-transitive_graph dbr:Vizing's_theorem dbr:Decision-to-decision_path dbr:Double_Cut_and_Join_Model dbr:Ear_decomposition dbr:Incidence_coloring dbr:Incidence_geometry dbr:Induced_path dbr:Induced_subgraph dbr:Induced_subgraph_isomorphism_problem dbr:Intelligence_cycle dbr:Interlocking_directorate dbr:Kuratowski's_theorem dbr:Kőnig's_lemma dbr:Level_ancestor_problem dbr:List_of_graphs dbr:Signed_graph dbr:Pseudoforest dbr:Weighted_automaton dbr:1-center_problem dbr:Color-coding dbr:Complete_graph dbr:Connectivity_(graph_theory) dbr:Analytic_Combinatorics dbr:Maximal_independent_set dbr:Maximum_flow_problem dbr:Nearest_neighbor_graph dbr:Multidimensional_network dbr:Pursuit–evasion dbr:GameMaker dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Mixed_graph dbr:Connectedness dbr:Basis_path_testing dbr:Berge's_theorem dbr:Line_graph dbr:Shortest_path_problem dbr:Cluster_analysis dbr:Component_(graph_theory) dbr:Halin's_grid_theorem dbr:Hamiltonian_coloring dbr:Kernelization dbr:Path dbr:Petri_net dbr:Matching_polynomial dbr:Thue_number dbr:Aczel's_anti-foundation_axiom dbr:Tree_(graph_theory) dbr:Walk_(graph_theory) dbr:Widest_path_problem dbr:Distance dbr:Gammoid dbr:Hackenbush dbr:Heavy_path_decomposition dbr:K-vertex-connected_graph dbr:Linear_temporal_logic dbr:Szymanski's_conjecture dbr:Promise_problem dbr:Transitive_reduction dbr:Adjacency_matrix dbr:Cyclomatic_complexity dbr:Edge-graceful_labeling dbr:Fractional_cascading dbr:Balance_theory dbr:Carbon_nanotube dbr:Causal_Markov_condition dbr:Centrality dbr:Directed_graph dbr:Graph-structured_stack dbr:Graph_kernel dbr:Graph_pebbling dbr:Graph_property dbr:Hirsch_conjecture dbr:Iterative_deepening_A* dbr:Kempe_chain dbr:Tree_structure dbr:Length dbr:Strongly_connected_component dbr:Reachability dbr:Regular_tree_grammar dbr:Hamiltonian_path dbr:Handshaking_lemma dbr:Hierarchy dbr:Smith_graph dbr:Biological_basis_of_personality dbr:Biological_network_inference dbr:Blossom_tree_(graph_theory) dbr:TRANUS dbr:Cograph dbr:Edge_contraction dbr:Edge_recombination_operator dbr:Thin_group_(combinatorial_group_theory) dbr:Red–black_tree dbr:Directed_acyclic_graph dbr:Directed_path_(graph_theory) dbr:Distance_(graph_theory) dbr:Pointer_jumping dbr:Indigo_(board_game) dbr:Minimum_spanning_tree dbr:Caterpillar_tree dbr:Ramsey's_theorem dbr:Search_algorithm dbr:Self-avoiding_walk dbr:Christofides_algorithm dbr:Longest_path_problem dbr:Longest_uncrossed_knight's_path dbr:Loop-erased_random_walk dbr:Six_degrees_of_separation dbr:Unavoidable_pattern dbr:Nearest-neighbor_chain_algorithm dbr:Traffic_flow_(computer_networking) dbr:Factor-critical_graph dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_unsolved_problems_in_mathematics dbr:Planarization dbr:Point_location dbr:Transit_node_routing dbr:Finite_topological_space dbr:Mountain_climbing_problem dbr:Polygonal_chain dbr:Polyhedral_graph dbr:Sidorenko's_conjecture dbr:Rainbow_coloring dbr:Panconnectivity dbr:Topology_(electrical_circuits) dbr:Wagner's_theorem dbr:Zero-suppressed_decision_diagram dbr:Star_coloring dbr:Temporal_network dbr:Simple_path dbr:Dipath dbr:Directed_path dbr:Path_(graph) dbr:Edge_independent_path dbr:Simple_path_(graph_theory) dbr:Vertex_independent_path |
| is foaf:primaryTopic of | wikipedia-en:Path_(graph_theory) |
