- Kombinatorika
- Halmazok, rendezett párok, leképezések
- Matematikai logika, ítéletkalkulus
- Gráfelméleti alapok
- Gráfok izomorfiája és síkbarajzolhatósága
- Gráfok bejárása és gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózatok
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
- Teljes indukció
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák
- Mátrixok
- Lineáris egyenletrendszerek
- Determinánsok
- Komplex számok
- Polinomok
- Interpolációs polinomok
- Csoportok, gyűrűk, testek
Gráfelméleti alapok
Csúcs fokszáma
A gráf egy csúcsának fokszáma a gráf e csúcsában összefutó élek száma.
Egyszerű gráf
Egy gráf egyszerű, ha nincs benne sem többszörös él, sem hurokél.
Fa
Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.
Egy $n$ csúcsú fának mindig $n-1$ darab éle van.
Gráfelméleti kör
Egy gráfban körnek nevezünk egy olyan utat, amely csupa különböző csúcsokon és éleken haladva visszavezet a kiinduló csúcsába.
Összefüggő gráf
Egy gráf összefüggő, ha bármelyik csúcsából el lehet jutni bármelyik másik csúcsába élek mentén.
Teljes gráf
Azokat a gráfokat, ahol minden csúcs mindegyikkel össze van kötve, teljes gráfnak hívjuk.
Az $n$ csúcsú teljes gráf éleinek a száma:
\( \frac{ n (n-1)}{2} \)
Euler-kör
Egy gráf Euler-köre olyan zárt élsorozat, amely a gráf összes élét pontosan egyszer tartalmazza.
Mik azok a gráfok? Megtanuljuk, hogy mik az Egyszerű gráfok, Csúcsok, Élek, Út, Kör, Összefüggő gráfok, Izolált pont, Körmentes gráfok, Fa. Valamint megnézzük, mire lehet használni a gráfokat a valóságban. A híres königsbergi hidak problémával kezdjük, aztán nézünk néhány példát, hogyan lehet gráfokkal jellemezni mondjuk egy épület termeit. Végül pedig nézzük, hogyan alkotható meg egy gráf, ha ismerjük a csúcsainak fokszámát. Itt jön néhány gráfalkotó algoritmus és néhány trükk, amit érdemes tudni a gráfalkotó feladatok megoldásánál.
