A grafikonelmélet elemei
3. 3. A szomszédságok listája. 14
4. Grafikus átmenetek. 14
4. 1. Keressen alaposan. 15
4. 2. Keresés szélességben. 17
Hivatkozásokat. 20
Bármely rendszer, amely feltételezi a különálló állapotok jelenlétét vagy a csomópontok és átmenetek jelenlétét közöttük, egy grafikonon keresztül írható le.
Az első grafikonelmélet, amely a híres svájci L. Euler matematikushoz tartozik, 1736-ban jelent meg. Euler egy nagyon híres rejtvényt oldott meg a Koenigsberg hidakról. A "számlálás" kifejezést először 200 éves (1936-ban) D. Kenigot bevezette. A gráfelmélet fejlődését a huszadik és huszadik század fordulóján stimulálták, amikor a topológia és kombinatorika területén végzett munkák száma élesen nőtt, amellyel a rokonság legszorosabb kapcsolatai kapcsolódtak. A grafikonokat az áramkörök és a molekuláris áramkörök építésénél használják.
Különálló matematikai fegyelemként a grúzelméletet először a magyarországi Koenig matematikus munkájában mutatta be az 1930-as években.
A közelmúltban a grafikonok és a kapcsolódó kutatási módszerek szinte minden szinten szervesen behatolnak szinte minden modern matematikába. A grafikonokat hatékonyan használják a tervezés és menedzsment elméletében, az ütemezés elméletében, a szociológiában, a közgazdaságtanban, a biológiában, az orvostudományban, a földrajzban. A grafikonok a széles körben használt területeken, mint a programozás, az elektronika, foglalkozó valószínűségi és a kombinatorikus problémák, megtalálni a legrövidebb távolság, maximális egyezés, és mások. Math szórakoztató és rejtvényeket is részét képezik a gráfelmélet. A grafikonelmélet gyorsan fejlődik, minden új alkalmazást megtalál.
1. Alapfogalmak
A két A és B sorozatú Descartes termék az elemek párosa, így a páros első eleme az A készletből, a második B: A x B = -ból származik.
Például az A = és B = halmazok Descartes-terméke az A x B = <(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)>.
A grafikon egy pár G = (V, E), ahol V a csúcsok halmaza, E a szélek (ívek).
A grafikon egy véges számú pont gyűjteménye, amelyet egy gráf csúcsai hívnak össze, és párhuzamosan összeköti a vonalak egyik csúcsát, amelyet egy gráf éleinek vagy éleinek neveznek.
A gráf csúcsait latin, A, B, C, D betűkkel vagy számokkal jelölik. Néha egy gráf egészét egy nagybetűvel jelölheti.
Egy rendezetlen csúcspontot egy ív által elrendezett élnek neveznek. Ez azt jelenti, hogy a csúcsok között, amelynek iránya van, ívnek nevezzük. Az irányt egy nyíllal jelöltük a végén.
A szegmensek között, amelyeknek nincs iránya, az élnek nevezik.
Az ívek olyanok, mint az egyirányú utak: csak egy irányba tudsz vezetni. A bordák olyanok, mint a kétirányú utak: mindkét irányban vezethet.
A grafikonok segítségével egyszerűsíthetjük a tudás különböző területein megfogalmazott problémák megoldását: az automatizálás, az elektronika, a fizika, a kémia stb. A grafikonok bemutatják az utak, a gázvezetékek, a hő és a villamosenergia-rendszereket. A grafikonok segítenek a matematikai és gazdasági problémák megoldásában.
Arkady, Borisz. Vladimir, Grigory és Dmitry az ülésen kézfogásokat cseréltek (mindegyik egyszer kezet rázott). Hány kézfogás történt?
Az A, B, B, F, D pontokat a gráf csúcsainak nevezzük, és ezek a pontok összekötő szegmensek a grafikon élei.
A probléma során az ábrán látható grafikon széleinek számát kell kiszámítani. Ez a szám megegyezik a tökéletes kézfogások számával az öt fiatal között. Vannak 10 közülük.
Az íveket tartalmazó grafikon csak orientáltnak nevezhető.
Az orientált egy grafikon, amelyben az x (y) formájú függőleges párok sorozata, ahol x az eleje, y az ív vége. Az ív (x, y) gyakran az alábbi formában látható:
Úgy véljük, hogy az ív az x csúcsról az y csúcsra vezet, és az y csúcs az x csúcs szomszédságában van. Egy orientált gráfot szintén digraphnak neveznek.