„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
alapfogalmak |
|||
8. sor:
== Alapfogalmak ==
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.
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 csúcsok között haladó különböző élek.
Egy ''G'' gráf '''részgráf'''ja olyan gráf, ami ''G'' bizonyos csúcsaiból és azok között bizonyos éleiből áll. Ha ''G'' egyes csúcsai között haladó ''összes'' élt vesszük, akkor '''feszített részgráf'''ról beszélünk.
16 ⟶ 18 sor:
Az '''út''' élek egymáshoz csatlakozó sorozata, amely egy csúcsot legfeljebb egyszer tartalmaz. A '''kör''' élek egymáshoz csatlakozó sorozata, ami záródik, tehát az utolsó és az első élnek van közös végpontja, és nincs ismétlődő csúcs. Ha csak élek ismétlődését zárjuk ki, akkor '''ciklus'''ról beszélünk.
A gráfok csúcsai, élei kaphatnak különböző racionális számokat is, különböző jelentésekkel: kapacitás, súly, illetve költség.
A Petri-hálók gráfok, kétféle csúccsal.
A gráfokhoz hasonló konstrukciók a hipergráfok, melyekben az élek mérete nincs korlátozva.
== Összefüggőség ==
Egy gráfot ''összefüggő''nek nevezünk, ha bármely két különböző csúcsa között halad út.
55 ⟶ 62 sor:
{{bővebben|Gráfok színezése}}
A gráfok csúcsai és élei színezhetők, azaz osztályokba oszthatók. Az egyes csoportokat jelölhetik a színek, vagy számok.
Egy gráf ''jó színezés''e a szögpontjainak bármilyen olyan színezése, amiben összekötött csúcsok különböző színeket kapnak. Egy ''G'' gráf ''kromatikus szám''a a ''G'' jó színezéseihez szükséges színek minimális száma, jelben: <math>\chi(G)</math>.
94 ⟶ 103 sor:
== Részterületek ==
* Algoritmikus gráfelmélet: A gráfokon működő algoritmusokkal foglalkozik. Például Dijsktra-algoritmus.
* Kémiai gráfelmélet: Az egyik legkorábbi alkalmazás, ami molekulákat vizsgál gráfelméleti szempontból.
* Extremális gráfelmélet: Egy adott osztályba tartozó gráfok közül melyek minimalizálnak vagy maximalizálnak egy bizonyos gráfparamétert? Egy fontos eredménye a [[Turán-tétel]].
* Geometriai, illetve topologikus gráfelmélet: Gráfokat ágyaznak bele geometriai és topologikus alakzatokba. Például meghatározza a síkba rajzolhatóság feltételeit.
* Hálózatkutatás: Tapasztalati úton vizsgál különböző gráfokat, melyek különböző alkalmazási területekről származnak, mint szociológia, közgazdaság, biológia és epidemiológia. Például a betegségek terjedése és a szociális kapcsolatok. Sok hálózat kicsi világ tulajdonságú, azaz bármely két pontja között rövid az út a pontok számához képest.
* Spektrális, más néven algebrai gráfelmélet: A gráfok szomszédsági és Laplace-mátrixának sajátértékei, sajátvektorai és karakterisztikus polinomjai és a gráftulajdonságok kapcsolatát kutatja. A nem irányított gráfok sajátértékei valósak, mivel szomszédsági mátrixuk szimmetrikus. A gráfok szomszédsági mátrixánek sajátértékei alkotják a gráf spektrumát, ami független a gráf csúcsainak sorrendjétől a mátrixban.
=== Véletlen gráfok ===
'''Tétel:''' Ha egy egyszerű véges gráf minden pontjának foka legalább 2 akkor van kör a gráfban.
108 ⟶ 117 sor:
'''Általánosítás:''' Ha egy egyszerű véges gráf minden pontjának foka legalább k, akkor van legalább k+1 pontot tartalmazó kör.
'''Tétel:''' Ha egy 2n pontú gráf minden pontjának foka legalább n, akkor a gráf összefüggő.
| |||