Multimediaexpo.cz je již 18 let na českém internetu !!
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ů 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. 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.
| 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. |