Tranzitív lezárás

Egy reláció tranzitív lezárása az a legkisebb reláció, amely tartalmazza az eredeti relációt, és teljesíti a tranzitivitás feltételét. Vagyis ha az eredeti relációban van egy a → b és b → c kapcsolat, akkor a tranzitív lezárásban mindig szerepel a → c kapcsolat is.

Formális definíció

Itt Rⁿ az n-szeres kompozícióját jelenti a relációnak önmagával. A tranzitív lezárás tehát minden olyan kapcsolatot tartalmaz, amely véges hosszúságú láncolattal elérhető az eredeti relációból.

Példa

Legyen A = {1,2,3,4}, R = { (1,2), (2,3), (3,4) }.

A tranzitív lezárás R⁺ = { (1,2), (2,3), (3,4), (1,3), (2,4), (1,4) }, mert (1,3) következik a (1,2) és (2,3)-ból, (2,4) a (2,3) és (3,4)-ből, és (1,4) a (1,3) és (3,4)-ből vagy hosszabb láncokból.

Tulajdonságok

• A tranzitív lezárás mindig tranzitív.
• A tranzitív lezárás tartalmazza az eredeti relációt: R ⊆ R⁺.
• A tranzitív lezárás a legkisebb tranzitív reláció, amely tartalmazza R-t.
• Ha R már tranzitív, akkor R⁺ = R.

Gráfos értelmezés

A gráfelméletben a tranzitív lezárás azt mutatja meg, hogy egy adott pontból mely pontok érhetők el útvonalakon keresztül. Például ha van egy út A-ból B-be és B-ből C-be, akkor a tranzitív lezárás tartalmazza az A-ból C-be vezető kapcsolatot is.

Összefoglalás

A tranzitív lezárás egy reláció olyan kiegészítése, amely biztosítja a tranzitivitást, és a lehető legkevesebb új elemet adja hozzá. Ez a fogalom kulcsfontosságú a matematikában, az algoritmusokban és a gráfelméletben is.

Gyakorló feladat