REAL

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.

[img]
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).

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: János Boromisza
Date Deposited: 25 Jul 2024 11:07
Last Modified: 25 Jul 2024 11:07
URI: https://real.mtak.hu/id/eprint/200901

Actions (login required)

Edit Item Edit Item