„Gráfelmélet” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
További osztályok |
|||
8. sor:
== Alapfogalmak ==
{{fő|Gráfelméleti fogalomtár}}
A gráfelmélet alapfogalma a '''[[gráf]]''', olyan [[Matematikai struktúra|struktúra]], ami '''csúcs'''okból vagy szögpontokból és '''él'''ekből áll, minden él két (esetleg egybeeső) csúcs között fut. Irányított gráfok esetén ezek a csúcspárok rendezettek. Többnyire azonban gráfon irányítatlan gráfot értenek; ha a gráf irányított, azt külön jelzik. Két csúcs szomszédos, hogyha van köztük él, azaz elemei ugyanannak az élnek. Egy él összeköt két pontot, ha a pontok elemei az élnek.
45 ⟶ 46 sor:
A [[Arthur Cayley|Cayley]]-tétel szerint adott ''n'' csúcson pontosan <math>n^{n-2}</math> fa van.
Ha egy gráf összes összefüggőségi komponense fa, akkor az '''erdő'''. Ekvivalensen, a körmentes gráfok erdők.
Irányított gráfok esetén a fák szerepét irányított körmentes gráfok, illetve '''fenyők''' veszik át.
== Többszörösen összefüggő gráfok ==
75 ⟶ 80 sor:
[[Fájl:csx graf ut.jpg|thumb|center|400px|példa]]
==Páros gráf==
Egy gráf [[páros gráf|páros]], ha nincs benne páratlan hosszúságú kör. Ekvivalensen, a gráf csúcsai két halmazba oszthatók úgy, hogy az összes él a két halmaz között fut
Jegyezzük meg, hogy mivel a fák körmentesek, azért a fák is páros gráfok.
82 ⟶ 87 sor:
{{bővebben|Síkbarajzolható gráf}}
gráf duálisa, [[Kuratowski-tétel|Kuratowski tétele]], felületre rajzolhatóság
==További osztályok==
* [[Reuláris gráf]ok]: Minden csúcsnak ugyanannyi szomszédja van.
* [[Merev körű gráf]]ok
* [[Perfekt gráf]]ok
* [[Mágikus gráf]]ok
== Ramsey-elmélet ==
A [[Ramsey-tétel]] gráfokra vonatkozó speciális esete a következő:
118 ⟶ 127 sor:
A különböző tulajdonságok kapcsolatban állnak egymással. Például a csúcsösszefüggőségi szám nem lehet nagyobb, mint az élösszefüggőségi szám; ez pedig szintén nem nagyobb, mint a gráf minimális foka. Síkgráfokban a kromatikus szám nem nagyobb, mint négy; lásd négyszíntétel.
A felsorolt gráftulajdonságok egy része relatív gyorsan meghatározható, a csúcsok számának másodfokú függvényével növekvő időben. Más tulajdonságokra nem ismert hasonlóan gyors algoritmus, évtizedekbe kerülne kisebb gráfoknál is. Itt jön képbe a heurisztika, amivel értelmes közelítő megoldások nyerhetők.
=== Véletlen gráfok ===
| |||