imported>Ulanwp: Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert

2026-04-04T10:25:26Z

Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert

Neue Seite

[[Datei:Path-graph.svg|mini|250px|right|Der lineare Graph <math>P_6</math>]]

Ein '''linearer Graph''' oder '''Pfadgraph''' ist ein [[Graph (Graphentheorie)|Graph]], der nur aus einem [[Pfad (Graphentheorie)|Pfad]] besteht. Lineare Graphen sind einfache Beispiele für [[Baum (Graphentheorie)|Bäume]]. Sie haben keine Verzweigungen, sodass die mittleren [[Knoten (Graphentheorie)|Knoten]] den Grad 2, und die Endknoten den Grad 1 haben. Der lineare Graph mit <math>n</math> Knoten wird mit <math>P_n</math> bezeichnet.

== Graziöse Beschriftung ==
Lineare Graphen sind [[Graziöse Beschriftung|graziöse Graphen]].<ref>{{cite journal |author=Michelle Edwards, Lea Howard |date=2006 |title=A survey of graceful trees |journal=Atlantic Electronic Journal of Mathematics |volume=1 |issue=1 |pages=5–29 |url=http://euclid.trentu.ca/aejm/V1N1/Edwards.v1n1.pdf |language=en}} </ref> Eine graziöse Beschriftung entsteht, wenn die Knoten mit den Zahlen <math>1, n, 2, n-1, 3, n-3, \ldots</math> beschriftet werden. Diese Beschriftung ist bipartit.
:[[Datei:Graceful_labeling_of_linear_graphs.svg]]
Eine entsprechende graziöse Beschriftung für den linearen Graphen mit fünf Knoten zeigt die folgende Zeichnung.
:[[Datei:Graceful_labeling_of_P_5.svg]]

== Siehe auch ==
* [[Kreisgraph]]
* [[Sterngraph]]
* [[Leitergraph]]

== Einzelnachweise ==
<references />

[[Kategorie:Bäume und Wälder]]

Linearer Graph - Versionsgeschichte

imported>Ulanwp: Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert