Mi a grafikonok módszere?
Mi a grafikonok módszere?
A "grafikon" szó a matematikában azt a képet jelenti, amelyben több pontot rajzolunk, amelyek közül néhány vonalakkal van összekapcsolva. Először is, azt kell mondanunk, hogy a grafikonok, amelyekről megvitatják, a múlt arisztokráciáihoz semmi közük sincs. A "grafikonaink" a görög "grafó" szóval rendelkeznek, ami azt jelenti, hogy "írok". Ugyanaz a gyökér a "menetrend", "életrajz" szavakban.
A matematika esetében a gráf definíciója a következő: egy gráf véges pontkészlet, amelyek közül néhány vonalakkal van összekapcsolva. A pontokat a gráf csúcspontjainak nevezzük, és az összekötő vonalak neve élek.
Az "elszigetelt" csúcsokat tartalmazó gráf-sémát zérus gráfnak nevezik. (2. ábra)
Azok a grafikonok, amelyekben az összes lehetséges széle nincs felépítve, hiányos grafikonoknak nevezik. (3.
A grafikonok, amelyekben minden lehetséges széle épül, teljes grafikonnak nevezik. (4. ábra)
Egy grafikon, amelynek csúcsa bármely másik csúcs egyik széléhez van kötve, azt mondják, hogy teljes.
Felhívjuk a figyelmet arra, hogy ha a teljes grafikon n csúcsokkal rendelkezik, akkor az élek száma egyenlő
Valójában az n csúcshoz tartozó teljes gráfban lévő szélek számát úgy definiáljuk, mint a gráf összes n élpontjából álló rendezetlen párok számát, vagyis az n elemek kombinációinak számát 2:
Egy nem teljes grafikon teljes egészében ugyanazzal a csúcsokkal egészíthető ki, a hiányzó élek hozzáadásával. Például a 3. ábra öt csúcsú, hiányos grafikont mutat. A 4. ábrán azok a szélek, amelyek egy gráfot egy teljes grafikonká alakítanak át, egy másik színnel ábrázolják, a gráf csúcsainak halmazát ezekkel az élekkel gráf kiegészítéseként nevezik.
A csúcsok foka és az élek számának számítása.
A gráf csúcsából kilépő élek számát a csúcspontnak nevezzük. A furcsa fokú grafikon csúcsát különösnek nevezik. és egyenletes mértékben - még.
Ha a grafikon összes csúcsa egyenlő, akkor a grafikon homogén. Így minden teljes grafikon homogén.
Az 5. ábra öt csúcsot ábrázol. Az A csúcs fokát St. A. jelöli.
Az ábrán. St.A = 1, St.B = 2, St.V = 3, St.G = 2, Std.D = 0.
Formázzunk bizonyos szabályzatokat, amelyek bizonyos grafikonokban rejlenek.
A teljes gráf csúcspontjai azonosak, és mindegyikük egy kisebb, mint a grafikon csúcsainak száma.
Ez a mintázat nyilvánvaló a teljes grafikon megfontolása után. Minden csúcsot minden csúcsra szegélyezünk, kivéve magát, vagyis az n csúcsok gráfjának minden csúcsából n-1 él ébreszt, ami ezt bizonyítani kell.
A grafikon csúcspontjainak összege egyenlő, egyenlő a grafikon éleinek kétszeresével.
Ez a minta nem csak a teljes, hanem bármilyen grafikonra érvényes. bizonyíték:
Valójában a gráf minden szegélye két csúcsot köti össze. Tehát, ha összeadjuk a fokok száma minden a gráf, megkapjuk kétszer élek számát 2R .. (R - élek száma), hogy minden él kétszer számították, szükség
A grafikon páratlan csúcsainak száma egyenletes. bizonyíték:
Vegyünk egy tetszőleges grafikonot Γ. Tegyük fel, hogy ebben a gráfban olyan csúcsok száma, amelyeknek az 1 fokszáma egyenlő K1-vel; a 2. fokozatú csúcsok száma K2-vel egyenlő; ; azoknak a csúcsoknak a száma, amelyeknek n értéke egyenlő Kn-vel. Ezután a grafikon csúcspontjainak összege a következőképpen írható:
K1 + 2K2 + ZK3 +. + nKn.
Másrészt: ha az R gráf éleinek száma, akkor a szabályosságból 2 ismeretes, hogy a gráf összes csúcsainak összege megegyezik a 2R értékkel. Ezután egyenletet írhatunk
K1 + 2K2 + ZK3 +. + nKn = 2R. (1)
Az egyenlőség bal oldalán az összeg egyenlő a grafikon páratlan csúcsainak számával (K1 + K3 +.):
K1 + 2K2 + ZK3 + 4K4 + 5K5 +. + nK = 2R,
(K1 + K3 + K5 +.) + (2K2 + 2X3 + 4K4 + 4K5 +) = 2R
A második keret páros szám, mint páros számok összege. Az így kapott összeg (2R) páros szám. Ezért (K1 + K3 + K5 +.) Páros szám.
Tekintsük át a grafikonok segítségével megoldott problémákat:
Az osztály elsőbbsége. A pályaasztal bajnokságában 6 résztvevő: Andrey, Boris, Victor, Galina, Dmitry és Elena. A bajnokságot körkörös rendszerként tartják - a résztvevők mindegyike egyszerre játszik egymással. Eddig játszottak már néhány játékot: Andrej játszott Borisz, Galina és Elena; Boris, ahogy már említettük, Andreivel és Galinával; Victor - Galina, Dmitry és Elena; Galina Andreyval és Boriszral; Dmitrij - Victor és Elena - Andrew és Victor. Hány játékot eddig tettek és mennyi maradt?
Vita. A feladat adatait diagram formájában ábrázoljuk. A résztvevőket pontok képviselik: Andrew - A pont, Boris - B pont stb. Ha két résztvevő már egymás között játszott, akkor a pontokat szegmensenként ábrázoló pontokat összekapcsoljuk. Az 1. ábrán látható áramkört kapjuk.
Az A, B, B, D, D, E pontok a szegmensekhez csatlakozó grafikon csúcsai - a grafikon élei.
Ne feledje, hogy a grafikon éleinek metszéspontjai nem csúcspontjai.
Az eddig játszott játékok száma megegyezik az élek számával, azaz az élek számával. 7.
Az összetévesztés elkerülése végett a grafikon teteje gyakran nem pontokban, hanem kis körökben jelenik meg.
Ahhoz, hogy megtalálja a játékok számát, amelyek elvégzésére, építésére újabb grafikon ugyanolyan csúcsok, de a bordák csatlakozni fog a résztvevők, akik nem játszottak egymással (2. ábra) élére a grafikonon fordult 8, majd a bal tölteni 8 játék : Andrew - Victor és Dmitry; Borisz - Victor, Dmitry és Elena stb.
Próbáljunk meg egy grafikont készíteni a következő probléma által leírt helyzetre:
Probléma: Ki játszik Lyapkin-Tyapkinnak? Az iskolai dráma körében úgy döntött, hogy felállítja Gogol "felügyelőjét". Aztán kitört egy fűtött érv. Mindez Lyapkinnal - Tyapkinnel kezdődött.
- Lyapkinym - Tyapkinym fogom! Mondta Gene határozottan.
- Nem, én Lyapkin-Tyapkin leszek, Dima visszautasította. "A korai gyermekkorból álmodtam arról, hogy ez a kép a színpadon készült."
- Nos, jó lemondani ez a szerep, ha megengedik, hogy Khlestakov-ot játszhassam - mutatta Gen generositásának.
- ... És én - Osip, - nem adtam neki nagylelkűséggel Dima.
- Eper vagy kormányzó akarok lenni - mondta Vova.
- Nem, én vagyok a kormányzó - kiáltotta Alik és Borya kórusban. - Vagy Khlestakov, -
egyszerre adták hozzá.
A szerepeket elosztják, hogy az előadók boldogok legyenek?
Vita. Mi képviseli fiatal színészek a felső sorban a körök: A - Alik, B - Boris, The - Vova, D - Gene, D - Dima, a szerepeket, hogy fognak játszani - körökben a második sorban (1 - Lyapkin - Tyapkin 2 - Khlestakov 3 - Osip, 4 - Eper, 5 - Kormányzó). Ezután minden résztvevőből kivágjuk a szegmenseket, azaz bordát, a szerepeket, amelyeket ő szeretne játszani. Van egy tíz csúcsa és tíz széle (3. Ábra)
A probléma megoldásához öt olyan öt széle közül kell kiválasztania, amelyeknek nincs közös csúcsa. Könnyűvé tenni. Érdemes megjegyezni, hogy a 3. és 4. csúcsot egy él, az A és a B csúcsok vezetik. Ez azt jelenti, hogy az Osip (top 3) játssza Dima-t (aki más?), És Zemlyanichka-Vova-t. Vershina1 - Lyapkin - Tyapkin - kapcsolataikat ig D és E Rib 1 - D fizet, mert Dima már foglalt, az 1 - F, Lyapkin - Tyapkina játszani Gene. Továbbra is, hogy csatlakoztassa a csúcsokat A és B a csúcsok 2 és 5, a megfelelő szerepét az ellenőr és a polgármester. Ez kétféleképpen történhet: válaszd az A-5 és a B-2 élket, vagy az A -2 és a B -5 éleket. Az első esetben Alik fog játszani a kormányzó, és Boria - Khlestakova, a második esetben, éppen ellenkezőleg. Amint a grafikon látható, nincs más megoldás a problémára.
Ugyanaz a grafikon kapható a következő probléma megoldásakor:
A feladat. Meleg szomszédok. Az öt ház lakói egymással veszekedtek, és azért, hogy ne találkozzanak a kutakban, úgy döntöttek, hogy megosztják őket (kutakat), hogy minden ház tulajdonosa a "saját" kútjához menjen az "úton". Vajon képesek erre?
Felmerül a kérdés: vajon szükséges-e a szétszerelt problémák grafikonjai? Nem tudunk megoldást találni tisztán logikus módon? Igen, igen. De a grafikonok lehetővé tették a feltételek láthatóságát, egyszerűsítették a megoldást, és feltárta a feladatok hasonlóságát, a két feladatot egybe rendezve, és ez nem kevés. És most képzeld el azokat a feladatokat, amelyek gráfjainak 100 vagy több csúcsa van. De éppen ilyen feladatokat kell megoldani a modern mérnökök és közgazdászok. Itt nem lehet grafikonok nélkül.
III. Euler grafikái.
Grafikus elmélet - a tudomány viszonylag fiatal: Newton idején egy ilyen tudomány még nem létezett, bár voltak "genealógiai fák", amelyek során grafikus fajtákat ábrázoltak. A grafikonelmélet első munkája Leonard Eulerhez tartozik, és 1736-ban jelent meg a Szentpétervári Tudományos Akadémia kiadványaiban. Ez a munka a következő feladat figyelembevételével kezdődött:
a) A Koenigsberg hidak problémája. Koenigsberg (ma Kalinyingrád) városa a Pregel-folyó (Pregoli) partján és két szigetén helyezkedik el, a város különböző részein hét hidat kapcsoltak össze, amint az az ábrán látható. Vasárnaponként a polgárok sétálnak a városban. Lehet-e választani egy ilyen útvonalat, hogy egy-egy alkalommal és minden egyes hídon áthaladjon, majd visszatér az út kiindulópontjához?
Mielőtt megvizsgálnánk ezt a problémát, bemutatjuk az "Euler grafikonok" fogalmát.
Próbáljuk ki a 4. ábrán ábrázolt gráfot, kör egy lökettel. vagyis anélkül, hogy a ceruza a papírlapról elválna, és többször nem halad át a vonal ugyanazon részében.
Ez a szám, olyan egyszerű megjelenésű, mint kiderült, érdekes funkcióval rendelkezik. Ha elindítjuk a mozgást a B csúcsból, akkor biztosan megkapjuk. És mi történik, ha az A-ból indulunk? Ebben az esetben könnyű meggyőződni arról, hogy ebben a helyzetben nem tudunk körbejárni: mindig megmaradt bordák vannak, amelyeket nem lehet elérni.
Az 1. ábrán. Az 5. ábra egy grafikont mutat be, amelyet valószínűleg egyetlen lökettel lehet rajzolni. Ez egy csillag. Kiderül, hogy bár sokkal bonyolultabbnak tűnik, mint az előző grafikon, bármelyik csúcsról kiindulva körbefuthat.
A 6. ábrán rajzolt grafikonokat a toll ütemével is meg lehet húzni.
Most próbálj meg egy grafikont rajzolni, a 7. ábrán látható módon
Nem sikerült! Miért? Nem találja a jobb felsőt? Nem! Nem ez az. Ezt a grafikont nem lehet megrajzolni egy toll lökésével.
Olyan érveket fogunk végezni, amelyek meggyőzni fognak erről. Tekintsük az A csomópontot. Három csúcs jön ki belőle. Ebből a csúcsból rajzolunk egy grafikont. Ahhoz, hogy végigmenjenek ezeken a széleken, ki kell lépnünk az A tetejéről egy közülük, egy bizonyos ponton vissza kell térnünk a másodikba, és ki kell mennünk a harmadikba. De újra nem tudunk belépni! Ezért, ha elkezdünk rajzolni az A csúcsról, akkor nem tudjuk befejezni.
Tegyük fel, hogy az A csúcs nem kezdet. Ezután a rajzolási folyamat során be kell lépnünk az egyik bordába, másképp megyünk, és vissza kell térnünk a harmadikhoz. És mivel nem tudunk kilépni belőle, akkor az A csúcs ebben az esetben legyen a vég.
Tehát az A csúcsnak vagy a nyomvonal eredete vagy végső csomópontja lehet.
De ugyanazt mondhatjuk a grafikonunk három másik csúcsairól. Végül is a rajz kezdeti csúcsa csak egy csúcs lehet, és a végső csúcs is csak egy csúcs lehet! Tehát lehetetlen ezt a grafikát egyetlen löketben rajzolni.
A grafikont, amely a papíron levő ceruzát nélkül húzható, az Eulerian (6.
Az ilyen grafikonok Leonard Euler kutató után kaptak nevet.
Zakonomernost1. (a tételünkből következik).
Lehetetlen rajzolni egy páratlan számú páratlan csúcsú grafikont.
Rendszeresség 2.
Ha a grafikon összes csúcsa egyenletes, akkor a grafikát nem lehet a papírtól elválasztani ("egy löket"), csak egyszer rajzolva a rajzot. Elindíthatja a mozgást bármely csúcsról, és ugyanabban a csúcsban fejezheti be.
Rendszeresség 3.
Csak két páratlan csúcsból álló gráfot lehet rajzolni, anélkül, hogy a ceruza a papíron lenne, míg a mozgásnak e páratlan csúcsok egyikével kell kezdődnie, és a másodikban kell befejeznie őket.
Rendszeresség 4.
A több mint két páratlan csúcsú grafikon nem "egyetlen löketben" húzható.
Egy olyan ábrát (gráfot), amelyet a papíron levő ceruzát nem lehet levonni, egyszemélyesnek nevezik.
Egy gráfról azt mondják, hogy csatlakozik, ha bármelyik két csúcsa összekapcsolható egy úttal, vagyis egy sor szélekkel, amelyek mindegyike az előző végénél kezdődik.
Ha ezt a feltételt nem teljesítik, akkor egy lekapcsolt vonalnak nevezik a grafikont.
A 7. ábrán nyilvánvalóan diszjunkt grafikon látható. Ha például a D és az E csúcsa között éleket húzunk, akkor a grafikon összekapcsolódik. (Ábra8)
Az ilyen él a gráf elméletben (melynek eltávolítása után a kapcsolt vonal grafikáját leválasztott gráfvá alakítja) hídnak nevezik.
A 7. ábrán látható hidak példái lehetnek a DE, A3, BZ, stb. Bordák, amelyek mindegyike összekapcsolná a gráf "elszigetelt" részeinek csúcsait (8. ábra)
Az inkoherens gráf több "darabból" áll. Ezeket a "darabokat" a gráf kapcsolatának komponenseinek nevezik. Minden összekapcsolt komponens természetesen kapcsolt grafikon. Ne feledje, hogy a csatlakoztatott grafikonnak van egy csatlakoztatott összetevője.
Tétel.
A grafikon Euler, ha és csak akkor, ha csatlakoztatva van, és legfeljebb két páratlan csúcsa van.
A gráf rajzolásával minden csúcsot, kivéve az első és a végső értéket, ugyanakkora számokat adunk meg, mint ahogy hagyjuk. Ezért minden csúcsfokozatnak egyenlőnek kell lennie, kivéve kettőt, ezért az Euler gráfnak legfeljebb két páratlan csúcsa van.
Most térjünk vissza a Koenigsberg hidak problémájához.
A probléma megvitatása. Jelölje meg a város egyes részeit az A, B, C, D betűk és a hidak között - a város releváns részeit összekötő a, b, c, d, e, f, g - hidak. Ebben a feladatban, már csak egy hídon átkelők: áthalad minden híd, mi mindig egy része magunkat másokban, és fordítva, mozgó egyik városrészében egy másik, akkor inkább menj át a hídon. Ezért ábrázolják a város tervet egy gráf, amelynek csúcsai az A, B, C, D (8. ábra) azt mutatják, egyes részei a város, és az élek a, b, c, d, e, f, g - összekötő hidak a megfelelő részén . Gyakran kényelmesebb a széleket kényelmesebb módon ábrázolni, nem pedig egyenes vonalak, hanem ívelt ívek által.
Ha létezett egy olyan útvonal, amely kielégítette a probléma állapotát, akkor ez a gráf zárt, folytonos átmenete lenne, amely minden egyes élre egyszer átmegy. Más szavakkal, ezt a gráfot egy löketben kell megrajzolni. De ez nem lehetséges - nem számít, milyen a felső, úgy döntöttünk, az eredeti, van, hogy menjen át a többi tetején, és ugyanabban az időben minden „bejövő” él (a híd, amelyen beléptünk a városnak ezen a részén) fog megfelelni a „jön ki” él híd, amelyhez majd használja hagyni ezt a részét a város): az élek száma belépő minden csúcsában egyenlő az élek számát belőle, azaz az összes élek ülést minden csúcs kell még ... A grafikon nem felel meg ennek a feltételnek, ezért a szükséges útvonal nem létezik.
Azok számára, akik angolul tanulnak