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ů K2.

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. +more 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 G1 terminály s1 a t2 a graf G2 terminály s2 a t2.

Sériové spojení grafů G1 ⊙s G2 je graf, který spojuje terminály t1 a s2 a jako nové terminály má s1 a t2.

Paralelní spojení grafů G1 ⊙p G2 je graf, který spojuje terminály s1 a s2 do s, t1 a t2 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.

Kategorie:Typy grafů