Sériově paralelní graf

Třída sériově-paralelních grafů je tvořena grafy, které mohou vzniknout opakovaným použitím terminálových operací sériové spojení a paralelní spojení z grafů K₂.

Terminálové operace

m-ární k-terminálová operace je taková operace, která z m grafů s k vyznačenými vrcholy (terminály) vytvoří jediný graf s k terminály. Operace spojí grafy tak, že jednoznačným způsobem spojí některé terminály do jednoho. Terminál nového grafu smí být pouze jeden z původních terminálů nebo spojení několika z nich a to je též jednoznačně definováno operací.

Sériové a paralelní spojení

Nechť má graf G₁ terminály s₁ a t₂ a graf G₂ terminály s₂ a t₂.

Sériové spojení grafů G₁ ⊙_s G₂ je graf, který spojuje terminály t₁ a s₂ a jako nové terminály má s₁ a t₂.

Paralelní spojení grafů G₁ ⊙_p G₂ je graf, který spojuje terminály s₁ a s₂ do s, t₁ a t₂ do t a jako nové terminály má s a t.

Jedná se tedy o binární dvouterminálové operace.

Vlastnosti

Sériově-paralelní grafy jsou právě grafy stromové šířky nejvýše 2.