16. Tétel

Konvex sokszögek tulajdonságai. Szabályos sokszögek. Gráfok.

Teljes és szigorú kidolgozás az emelt szintű matematika érettségi szóbeli vizsgájára. Ez a tétel bemutatja a sokszögek alapvető tulajdonságait, az átlók és szögek kiszámítását, a szabályos sokszögeket, valamint bevezet a gráfelmélet alapjaiba, kitérve az elvárt bizonyításokra (pl. skatulyaelv alkalmazása gráfokra).

Konvex sokszögek tulajdonságai

Definíció: Egy síkidomot sokszögnek nevezünk, ha azt egy önmagát nem metsző, zárt törttvonal határolja. Egy sokszög konvex, ha bármely két pontját összekötő szakasz minden pontja a sokszög (vagy a határa) pontja. Ekvivalens megfogalmazásban: a konvex sokszög minden belső szöge kisebb, mint $180^\circ$.

Tétel: Egy $n$ oldalú konvex sokszög belső szögeinek összege $(n-2) \cdot 180^\circ$.

Bizonyítás: Válasszuk ki a sokszög egy tetszőleges csúcsát, és húzzuk meg az ebből a csúcsból kiinduló összes átlót. Mivel önmagába és a két szomszédos csúcsba nem húzható átló, így összesen $n-3$ átlót húzunk meg. Ezek az átlók a konvex sokszöget pontosan $n-2$ darab háromszögre bontják. Mivel a sokszög konvex, ezek a háromszögek lefedik a teljes sokszöget, és a háromszögek belső szögeinek összege pontosan kiadja a sokszög belső szögeinek összegét. Mivel egy háromszög belső szögeinek összege $180^\circ$, a sokszög belső szögeinek összege $(n-2) \cdot 180^\circ$. Q.E.D.

Tétel: Egy $n$ oldalú konvex sokszög átlóinak száma $\frac{n(n-3)}{2}$.

Bizonyítás: Egy $n$ csúcsú sokszög bármely csúcsából kiindulva pontosan $n-3$ átló húzható (mivel önmagába és a két közvetlen szomszédjába húzott szakasz nem átló, hanem él vagy pont). Mivel a sokszögnek $n$ csúcsa van, ez $n \cdot (n-3)$ db átló-végpontot jelent. Viszont így minden átlót pontosan kétszer számoltunk meg (mindkét végpontjából kiindulva), ezért a szorzatot el kell osztani kettővel. Így az átlók száma $\frac{n(n-3)}{2}$. Q.E.D.

További tulajdonság: Bármely konvex sokszög külső szögeinek összege $360^\circ$ (minden csúcsnál egy külső szöget figyelembe véve).

Szabályos sokszögek

Definíció: Egy konvex sokszöget szabályos sokszögnek nevezünk, ha minden oldala egyenlő hosszúságú (egyenlő oldalú) és minden belső szöge egyenlő nagyságú (egyenlő szögű).

  • Egy szabályos $n$-szög egyetlen belső szöge: $\alpha = \frac{(n-2) \cdot 180^\circ}{n}$.
  • Szimmetria: Minden szabályos $n$-szögnek $n$ darab szimmetriatengelye van. Ha $n$ páros, a sokszög középpontosan is szimmetrikus. Forgásszimmetriája $\frac{360^\circ}{n}$ fokos és annak többszörösei.
  • Körívek és körök: Minden szabályos sokszög húrsokszög (létezik körülírt köre, amely minden csúcsán átmegy) és érintősokszög (létezik beírt köre, amely minden oldalát érinti). A beírt és a körülírt kör középpontja egybeesik, ez a sokszög szimmetriaközéppontja.

Területszámítás: A szabályos $n$-szög felbontható $n$ darab egybevágó egyenlő szárú háromszögre, melyek csúcsa a sokszög középpontja. Ha a sokszög köré írt kör sugara $R$, egy ilyen háromszög területe $t = \frac{1}{2} R^2 \sin(\frac{360^\circ}{n})$. A teljes sokszög területe: $$T = n \cdot \frac{R^2}{2} \sin\left(\frac{360^\circ}{n}\right)$$

Gráfok alapfogalmai

Definíció: A gráf pontok (csúcsok) és az azokat összekötő vonalak (élek) halmaza. Jelölése: $G = (V, E)$, ahol $V$ a csúcsok (vertices), $E$ az élek (edges) halmaza.

  • Egyszerű gráf: Nincsenek benne többszörös élek (két csúcsot legfeljebb egy él köt össze) és nincsenek hurokélek (egy csúcsot önmagával összekötő él).
  • Fokszám ($d(v)$): Egy csúcsba befutó élek száma (hurokél kétszer számít, bár egyszerű gráfban ilyen nincs).
  • Séta, vonal, út, kör:
    Séta: Csúcsok és élek váltakozó sorozata.
    Út: Olyan séta, amelyben minden csúcs legfeljebb egyszer szerepel.
    Kör: Olyan séta, amelynek kezdő- és végpontja megegyezik, de minden más csúcsa különböző (legalább 3 hosszú egyszerű gráfban).
  • Összefüggő gráf: Bármely két csúcsa között létezik út.
Tétel (Kézfogás-lemma):

Bármely gráfban a csúcsok fokszámainak összege egyenlő az élek számának kétszeresével. Ebből következik, hogy a páratlan fokszámú csúcsok száma mindig páros.

$$\sum_{v \in V} d(v) = 2 \cdot |E|$$

Bizonyítás: Amikor a csúcsok fokszámait összeadjuk, minden egyes élt pontosan kétszer számolunk bele az összegbe: egyszer az egyik végpontjánál, egyszer pedig a másik végpontjánál. Így a fokszámösszeg pontosan az élek számának kétszerese. Mivel a fokszámösszeg páros szám ($2|E|$), és a páros fokszámok összege is páros, a páratlan fokszámú csúcsok fokszámainak összegének is párosnak kell lennie. Ez csak úgy lehetséges, ha páros sok páratlan fokszámú csúcs van. Q.E.D.

Fák, teljes gráfok és gráfelméleti tételek

Teljes gráf ($K_n$): Olyan egyszerű gráf, amelyben bármely két különböző csúcsot pontosan egy él köt össze. Egy $n$ csúcsú teljes gráf éleinek száma: $\binom{n}{2} = \frac{n(n-1)}{2}$.

Fa gráf: Összefüggő és körmentes gráf. Főbb tulajdonságai:
- Bármely két csúcsát pontosan egy út köti össze.
- Ha egy $n$ csúcsú gráf fa, akkor pontosan $n-1$ éle van ($|E| = |V| - 1$).

Tétel (Skatulyaelv alkalmazása gráfokra):

Bármely, legalább két csúcsú egyszerű gráfban mindig van (legalább) két azonos fokszámú csúcs.

Bizonyítás: Legyen a gráf csúcsainak száma $n \ge 2$. Mivel a gráf egyszerű, egy csúcs fokszáma minimálisan 0, maximálisan $n-1$ lehet. Tehát a lehetséges fokszámok halmaza: $\{0, 1, 2, ..., n-1\}$. Ez összesen $n$ darab különböző lehetséges érték.

Gondoljuk végig: lehet-e egy gráfban egyszerre $0$ fokszámú (izolált) csúcs és $n-1$ fokszámú (mindenki mással összekötött) csúcs? Nem, mert ha van egy $n-1$ fokszámú csúcs, az a gráf összes többi csúcsával (így a vizsgált másik csúccsal is) éllel van összekötve, tehát nem lehet a gráfban $0$ fokszámú csúcs.

Emiatt a gráf csúcsai ténylegesen csak legfeljebb $n-1$ különböző fokszámot vehetnek fel (vagy a $0$ hiányzik, vagy az $n-1$). Mivel azonban a gráfnak $n$ darab csúcsa van (ezek a "galambok"), de legfeljebb csak $n-1$ lehetséges fokszám osztható ki közöttük (ezek a "skatulyák"), a Dirichlet-féle skatulyaelv értelmében kell lennie legalább két olyan csúcsnak, amelyek ugyanazt a fokszámot ("skatulyát") kapják. Q.E.D.

Alkalmazások és Matematikatörténet

Az emelt szintű szóbeli vizsgán a kiváló értékeléshez elengedhetetlen a téma gyakorlati és történelmi vonatkozásainak ismerete.

Matematikatörténet (A gráfelmélet születése):

  • A gráfelmélet megalapítója Leonhard Euler volt. 1736-ban ő oldotta meg a híres königsbergi hidak problémáját. A kérdés az volt, hogy végig lehet-e menni a város 7 hídján úgy, hogy mindegyiken pontosan egyszer haladjunk át, és visszatérjünk a kiindulási pontra. Euler a szárazföldeket csúcsokkal, a hidakat élekkel modellezte, és bebizonyította, hogy mivel a csúcsok fokszáma páratlan, nem létezik ilyen séta (Euler-vonal/Euler-kör).
  • A reguláris (szabályos) sokszögek vizsgálata egészen az ókori görögökig, Püthagorasz és Eukleidész munkásságáig nyúlik vissza, utóbbi az Elemek című művében tárgyalta szerkeszthetőségüket.

Gyakorlati alkalmazások:

  • Informatika és hálózatok: A számítógép-hálózatokat (pl. az Internetet) hatalmas gráfokként modellezzük. A fák elmélete létfontosságú az adatbázisok keresőalgoritmusaiban (bináris keresőfák) és a hálózati útválasztásban (Spanning Tree Protocol).
  • Kémia: A molekulák szerkezetét gráfokkal írják le (a csúcsok az atomok, az élek a kémiai kötések). Például az alkánok szénhidrogénláncai matematikai értelemben fák. A gráfelmélet segítségével könnyen kiszámítható a lehetséges izomerek száma.
  • Építészet és Design: A szabályos sokszögek és konvex idomok elengedhetetlenek a mozaikozásoknál, kupolák és geodéziai dómok tervezésénél, mivel szimmetriájuk révén a terhelés egyenletesen oszlik el rajtuk.