Gráfelmélet
A Wikipédiából, a szabad lexikonból.
A gráfelmélet a matematika, ezen belül a kombinatorika egyik fontos ága. Kialakításához jelentős mértékben hozzájárultak a magyar kombinatorikai iskola tagjai: Kőnig Dénes, Erdős Pál, Gallai Tibor, Rényi Alfréd, Lovász László, Pósa Lajos.
Tartalomjegyzék |
[szerkesztés] Alapfogalmak
A gráfelmélet alapfogalma a gráf, olyan struktúra, ami csúcsokból vagy szögpontokból és élekből áll, minden él két csúcs között fut. Legtöbbször egyszerű gráfokkal foglalkozunk, azaz olyanokkal, amelyekben nincs hurokél (egy csúcsot önmagával összekötő él) és nincsenek párhuzamos élek sem, tehát azonos pontok között haladó különböző élek.
Egy csúcspont fokszáma a rá illeszkedő élek száma. Ha ez nulla, tehát az adott csúcsra nem illeszkedik él, akkor a csúcs izolált. Véges gráfok esetén a fokszámokat összeadva páros számot kapunk, hiszen ekkor minden élt kétszer számoltunk. Ha a fokszám minden csúcsra azonos, a gráf reguláris. Ha ez a közös fokszám k, akkor a gáf k-adfokú reguláris.
[szerkesztés] Euler-kör, Hamilton-kör
[szerkesztés] Fák
[szerkesztés] Összefüggőség
[szerkesztés] Párosítások, gráfok faktorai
[szerkesztés] Kromatikus szám
Brooks tétele, négyszín-tétel, Hadwiger-sejtés
[szerkesztés] Síkbarajzolhatóság
Kuratowski tétele
[szerkesztés] Ramsey-elmélet
[szerkesztés] Extremális gráfelmélet
[szerkesztés] Véletlen gráfok


Based on work by