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.
|
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 |