Sériově paralelní graf

Z Multimediaexpo.cz

Nemáte oprávnění „upravit tuto stránku“. Důvod:

Můžete si prohlédnout a zkopírovat zdrojový kód této stránky:

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 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ý rozklad#Stromová šířka|stromové šířky]] nejvýše 2. {{Článek z Wikipedie}} [[Kategorie:Typy grafů]]

Návrat na stránku „Sériově paralelní graf“.