Path graph (original) (raw)
Ein linearer Graph oder Pfadgraph ist ein Graph, der nur aus einem Pfad besteht. Lineare Graphen sind einfache Beispiele für Bäume. Sie haben keine Verzweigungen, sodass die mittleren Knoten den Grad 2, und die Endknoten den Grad 1 haben. Der lineare Graph mit Knoten wird mit bezeichnet.
| Property | Value |
|---|---|
| dbo:abstract | Ein linearer Graph oder Pfadgraph ist ein Graph, der nur aus einem Pfad besteht. Lineare Graphen sind einfache Beispiele für Bäume. Sie haben keine Verzweigungen, sodass die mittleren Knoten den Grad 2, und die Endknoten den Grad 1 haben. Der lineare Graph mit Knoten wird mit bezeichnet. (de) En teoría de grafos, un grafo camino es un grafo cuyos vértices forman un camino. El camino de cualquier grafo es un subgrafo que da como resultado un grafo camino. (es) In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are {vi, vi+1} where i = 1, 2, …, n − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2. Paths are often important in their role as subgraphs of other graphs, in which case they are called paths in that graph. A path is a particularly simple example of a tree, and in fact the paths are exactly the trees in which no vertex has degree 3 or more. A disjoint union of paths is called a linear forest. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See, for example, Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). (en) En théorie des graphes, un graphe chemin ou graphe chaîne (en anglais path graph) est un arbre où chaque nœud est de degré au plus deux. (fr) 그래프 이론에서 경로 그래프(經路graph, 영어: path graph)는 모든 꼭짓점의 차수가 2 이하인 나무이다. (ko) Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром. (ru) No campo da matemática da teoria dos grafos, um grafo caminho ou grafo linear é um exemplo particularmente simples de uma árvore, ou seja, uma árvore com dois ou mais vértices que não tem ramificações, ou seja, contém somente vértices de grau 2 e 1. Em particular, ela tem dois vértices terminais (vértices que têm grau 1), enquanto todos os outros (se houver) têm grau 2. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Path-graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ https://archive.org/details/graphtheorywitha0000bond/page/12 |
| dbo:wikiPageID | 4587190 (xsd:integer) |
| dbo:wikiPageLength | 3259 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094305224 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cycle_(graph_theory) dbr:Unit_distance_graph dbr:Degree_(graph_theory) dbr:Dynkin_diagram dbr:Complete_graph dbr:Mathematics dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Path_(graph_theory) dbc:Trees_(graph_theory) dbr:Tree_(graph_theory) dbr:Linear_forest dbr:Algebra dbr:Edge_(graph_theory) dbc:Parametric_families_of_graphs dbr:Null_graph dbr:Graduate_Texts_in_Mathematics dbr:Graph_theory dbr:Bipartite_graph dbr:Disjoint_union dbr:Caterpillar_tree dbr:Root_system dbr:Vertex_(graph_theory) dbr:Symmetric_group dbr:Weyl_group dbr:Path_decomposition dbr:File:Path-graph.svg |
| dbp:automorphisms | 2 (xsd:integer) |
| dbp:chromaticIndex | 2 (xsd:integer) |
| dbp:chromaticNumber | 2 (xsd:integer) |
| dbp:imageCaption | A path graph on 6 vertices (en) |
| dbp:name | Path graph (en) |
| dbp:properties | dbr:Unit_distance_graph dbr:Tree_(graph_theory) dbr:Bipartite_graph |
| dbp:title | Path Graph (en) |
| dbp:urlname | PathGraph (en) |
| dbp:wikiPageUsesTemplate | dbt:Interwiki_extra dbt:About dbt:Cite_book dbt:Distinguish dbt:Infobox_graph dbt:Math dbt:MathWorld dbt:Mvar dbt:Short_description dbt:Sub |
| dcterms:subject | dbc:Trees_(graph_theory) dbc:Parametric_families_of_graphs |
| rdf:type | owl:Thing yago:WikicatParametricFamiliesOfGraphs yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | Ein linearer Graph oder Pfadgraph ist ein Graph, der nur aus einem Pfad besteht. Lineare Graphen sind einfache Beispiele für Bäume. Sie haben keine Verzweigungen, sodass die mittleren Knoten den Grad 2, und die Endknoten den Grad 1 haben. Der lineare Graph mit Knoten wird mit bezeichnet. (de) En teoría de grafos, un grafo camino es un grafo cuyos vértices forman un camino. El camino de cualquier grafo es un subgrafo que da como resultado un grafo camino. (es) En théorie des graphes, un graphe chemin ou graphe chaîne (en anglais path graph) est un arbre où chaque nœud est de degré au plus deux. (fr) 그래프 이론에서 경로 그래프(經路graph, 영어: path graph)는 모든 꼭짓점의 차수가 2 이하인 나무이다. (ko) Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром. (ru) No campo da matemática da teoria dos grafos, um grafo caminho ou grafo linear é um exemplo particularmente simples de uma árvore, ou seja, uma árvore com dois ou mais vértices que não tem ramificações, ou seja, contém somente vértices de grau 2 e 1. Em particular, ela tem dois vértices terminais (vértices que têm grau 1), enquanto todos os outros (se houver) têm grau 2. (pt) In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are {vi, vi+1} where i = 1, 2, …, n − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See, for example, Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). (en) |
| rdfs:label | Linearer Graph (de) Grafo camino (es) Graphe chemin (fr) 경로 그래프 (ko) Path graph (en) Grafo caminho (pt) Путь (теория графов) (ru) Шлях (граф) (uk) |
| owl:differentFrom | dbr:Line_graph |
| owl:sameAs | freebase:Path graph yago-res:Path graph wikidata:Path graph dbpedia-de:Path graph dbpedia-es:Path graph dbpedia-fr:Path graph dbpedia-hu:Path graph dbpedia-ko:Path graph dbpedia-pt:Path graph dbpedia-ru:Path graph dbpedia-sq:Path graph http://ta.dbpedia.org/resource/பாதை_கோட்டுரு dbpedia-uk:Path graph https://global.dbpedia.org/id/54U3s |
| prov:wasDerivedFrom | wikipedia-en:Path_graph?oldid=1094305224&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Path-graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Path_graph |
| is dbo:wikiPageRedirects of | dbr:Linear_graph |
| is dbo:wikiPageWikiLink of | dbr:Schläfli_orthoscheme dbr:Mirsky's_theorem dbr:Wiener_index dbr:Dessin_d'enfant dbr:Hosoya_index dbr:Pathwidth dbr:Unit_distance_graph dbr:Incidence_poset dbr:Independent_set_(graph_theory) dbr:Molecular_geometry dbr:Robertson–Seymour_theorem dbr:15_puzzle dbr:Maximal_independent_set dbr:Skew_partition dbr:Strong_product_of_graphs dbr:Chromatic_polynomial dbr:Graph_bandwidth dbr:Graph_coloring_game dbr:Graph_homomorphism dbr:Graph_labeling dbr:Graph_minor dbr:Branch-decomposition dbr:Cop-win_graph dbr:Line_graph dbr:Skew-symmetric_graph dbr:Complement_graph dbr:PN dbr:Path_(graph_theory) dbr:Matroid_minor dbr:Threaded_binary_tree dbr:Tree_(graph_theory) dbr:Tree_decomposition dbr:Treewidth dbr:Trivially_perfect_graph dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Lattice_graph dbr:Linear_arboricity dbr:Linear_forest dbr:List_coloring dbr:Lollipop_graph dbr:Minimum_rank_of_a_graph dbr:Cycle_graph dbr:Cyclic_group dbr:Fence_(mathematics) dbr:Null_graph dbr:Graceful_labeling dbr:Graph_pebbling dbr:Graph_property dbr:Graph_state dbr:Graph_toughness dbr:King's_graph dbr:Order_dimension dbr:Tree-depth dbr:Handshaking_lemma dbr:Intersection_graph dbr:Uniquely_colorable_graph dbr:Starlike_tree dbr:Chordal_graph dbr:Ladder_graph dbr:Threshold_graph dbr:Dissection_into_orthoschemes dbr:Distance-hereditary_graph dbr:Split_graph dbr:Fibonacci_cube dbr:Grundy_number dbr:Cartesian_product_of_graphs dbr:Cartesian_tree dbr:Caterpillar_tree dbr:Cereceda's_conjecture dbr:Self-complementary_graph dbr:Matchstick_graph dbr:Simplex_graph dbr:Trajectory_inference dbr:Gyárfás–Sumner_conjecture dbr:Sumner's_conjecture dbr:Simultaneous_embedding dbr:Χ-bounded dbr:Radon's_theorem dbr:Twin-width dbr:Tadpole_graph dbr:Linear_graph |
| is owl:differentFrom of | dbr:Line_graph |
| is foaf:primaryTopic of | wikipedia-en:Path_graph |
