Sériově paralelní graf

Z Multimediaexpo.cz

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.

Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii