http://www.multimediaexpo.cz/mmecz/index.php?action=history&feed=atom&title=S%C3%A9riov%C4%9B_paraleln%C3%AD_grafSériově paralelní graf - Historie editací2026-05-25T15:25:00ZHistorie editací této stránkyMediaWiki 1.16.5http://www.multimediaexpo.cz/mmecz/index.php?title=S%C3%A9riov%C4%9B_paraleln%C3%AD_graf&diff=943802&oldid=prevSysop: + Nový článek2015-10-08T10:12:58Z<p>+ Nový článek</p>
<p><b>Nová stránka</b></p><div>Třída '''sériově-paralelních [[graf (teorie grafů)|grafů]]''' je tvořena grafy, které mohou vzniknout opakovaným použitím terminálových operací ''sériové spojení'' a ''paralelní spojení'' z&nbsp;grafů&nbsp;K<sub>2</sub>.<br />
<br />
== Terminálové operace ==<br />
''' ''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í.<br />
<br />
== Sériové a paralelní spojení ==<br />
Nechť má graf G<sub>1</sub> terminály ''s<sub>1</sub>'' a ''t<sub>2</sub>'' a graf G<sub>2</sub> terminály ''s<sub>2</sub>'' a ''t<sub>2</sub>''.<br />
<br />
'''Sériové spojení''' grafů G<sub>1</sub> ⊙<sub>s</sub> G<sub>2</sub> je graf, který spojuje terminály ''t<sub>1</sub>'' a ''s<sub>2</sub>'' a jako nové terminály má ''s<sub>1</sub>'' a ''t<sub>2</sub>''.<br />
<br />
'''Paralelní spojení''' grafů G<sub>1</sub> ⊙<sub>p</sub> G<sub>2</sub> je graf, který spojuje terminály ''s<sub>1</sub>'' a ''s<sub>2</sub>'' do ''s'', ''t<sub>1</sub>'' a ''t<sub>2</sub>'' do ''t'' a jako nové terminály má ''s'' a ''t''.<br />
<br />
Jedná se tedy o binární dvouterminálové operace.<br />
<br />
== Vlastnosti ==<br />
Sériově-paralelní grafy jsou právě grafy [[stromový rozklad#Stromová šířka|stromové šířky]] nejvýše 2.<br />
<br />
<br />
{{Článek z Wikipedie}}<br />
[[Kategorie:Typy grafů]]</div>Sysop