The Representation of a permutation as the Product of a Minimal Number of Transpositions, and its Connection with the Theory of Graphs = Permutációk minimális számú transzpozíció szorzatára bontásainak száma és ezek kapcsolata a gráfelmélettel

Dénes, József (1959) The Representation of a permutation as the Product of a Minimal Number of Transpositions, and its Connection with the Theory of Graphs = Permutációk minimális számú transzpozíció szorzatára bontásainak száma és ezek kapcsolata a gráfelmélettel. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 4 (1). pp. 63-71.

Preview

Text cut_MATKUTINT_4_1_1959_pp63_-_71.pdf Download (7MB) | Preview

Abstract

Cayley [3] cikkében található tétel szerint az n szögpontú fák száma nⁿ⁻³. Ebben a cikkben a szerző megmutatja az: n szögpontú fák száma megegyezik egy adott n-edfokú ciklus n — 1 transzpozíció szorzatára bontásainak számával (1. tétel). Legyen Cₙ egy adott n-edfokú ciklus n — 1 transzpozíció szorzatára bontásainak száma, akkor Cₙ = nⁿ⁻² (Korollárium). A 2. tétel Cₙ-re vonatkozó rekurzív összefüggést ad. A 4. tétel az összes k ciklust tartalmazó n-edfokú permutációk n — k transzpozíció szorzatára bontásainak számát állapítja meg. A 4. tétel gráfelméleti alkalmazása lehetővé teszi a k, páronként különböző és közös pont nélküli fákból mint részgráfból álló n szögpontú gráfok számának meghatározását (5. tétel).

Actions (login required)

Edit Item