Kezdőlap


Feladat:	F.2051	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1977/január, 9 - 10. oldal		PDF \| MathML
Témakör(ök):	Fagráfok, erdők, faváz, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1976/szeptember: F.2051

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Érdemes a feladatot általánosan igazolni. Legyen a feladat az, hogy $n$ tábor között $(n \geq 2)$ akarunk úthálózatot építeni. Előírunk $u_{1}, u_{2}, ..., u_{n}$ pozitív egész számokat úgy, hogy

\begin{matrix} u_{1} + u_{2} + ... + u_{n} = 2 \cdot n - 2. \end{matrix}

Megmutatjuk, hogy van olyan úthálózat, ami eleget tesz az a) és b) feltételnek, és a

T_{i}

táborból

u_{i}

út indul ki

(i = 1, 2, ..., n)

. A kitűzött feladat az

n = 51

-hez tartozó speciális esete az általános feladatnak.
Az állítást

n

-re vonatkozó teljes indukcióval igazoljuk.

n = 2

-re az állítás igaz, mert ekkor csak az

u_{1} = u_{2} = 1

számokat írhatjuk elő, és a

T_{1}

-et

T_{2}

-vel összekötő egyetlen útból álló úthálózat eleget tesz az a) és b) feltételeknek.
Tegyük fel, hogy

n \geq 2

-re igaz az állítás és mutassuk meg, hogy ebből következik, hogy

(n + 1)

-re is fennáll. Legyenek

u_{1}, ..., u_{n + 1}

tetszőleges pozitív egész számok, úgy hogy az összegük

2 n

legyen. Akkor van közöttük olyan, amelyik

1

, mert ha mindegyik

1

-nél nagyobb, akkor mindegyik legalább

2

, tehát összegük legalább

2 n + 2

, ami nem lehet. Van köztük olyan is, ami

1

-nél nagyobb, mert ha mindegyik

1

lenne, akkor összegük

n + 1

lenne, ami

n \geq 2

mellett

2 n

-nél kisebb. Válasszunk ki egy

u_{k} = 1

számot és egy

u_{j} > 1

-et. Az

u_{1}, ..., u_{n + 1}

, számok közül hagyjuk el

u_{k}

-t és

u_{j}

helyett írjunk

(u_{j} - 1)

-et. Így

n

pozitív egész számot kapunk, amelyeknek összege

2 n - 2

. Az indukciós feltevés szerint ezekhez van az a) és b) feltételeknek eleget tevő úthálózat. Adjunk meg egy ilyent és ezt egészítsük ki a

T_{k}

táborból a

T_{j}

-be vezető egyetlen úttal. Az

n + 1

tábort összekötő, így kapott úthálózat nyilvánvalóan teljesíti azt a feltételt, hogy

T_{i}

-ből

u_{i}

út indul ki

(i = 1, 2, ..., n)

. Eleget tesz az a) feltételnek is, mert egy ennek megfelelő úthálózatot egészítettünk ki egyetlen olyan úttal, amelyik két tábort köt össze és más tábort nem érint. Úthálózatunk eleget tesz a b) feltételnek is, mert bármely két

T_{k}

-tól különböző tábort választunk is ki, az egyikből a másikba pontosan egyféleképpen lehetett eljutni, s ezen a

T_{k}

-ból

T_{j}

-be vezető út felvétele nyilván nem változtat.

T_{k}

-ból is pontosan egyféleképpen juthatunk el bármely másik táborba úgy, hogy

T_{k}

-ból először

T_{j}

-be megyünk és, ‐ ha a másik kiválasztott tábor nem

T_{j}

, akkor ‐

T_{j}

-ből a másik táborba vezető egyetlen útvonalon megyünk tovább.

Megjegyzés. Ha a táborokat pontokkal szemléltetjük, az összekötő utakat pedig a pontokat összekötő vonalakkal, akkor egy gráfot kapunk. A feladat a) és b) feltételeinek eleget tevő gráfokat a gráfelméletben fáknak nevezik. Erről a témáról Rényi Alfréd most megjelent "Napló az információelméletről'' című kötetében érdekes cikk található a 164‐185. oldalakon "A fák matematikai elmélete'' címmel.