Pristatymas: Grafikai ir jų taikymas sprendžiant uždavinius. Pristatymas tema "grafai" Parsisiųsti pristatymą kas yra grafikas
Grafas yra baigtinė viršūnių V aibė ir briaunų aibė R, jungianti viršūnių poras, G=(V,R). Aibių V ir R kardinalumai lygūs N ir M. Kraštinių aibė gali būti tuščia. Viršūnių pavyzdžiai yra bet kokio pobūdžio objektai (gyvenvietės, kompiuterių tinklai). Kraštų pavyzdžiai yra keliai, bortai, linijos.
Viršūnės, sujungtos briauna, vadinamos gretimomis. Briaunos, turinčios bendrą viršūnę, taip pat vadinamos gretimomis. Briauna ir bet kuri iš dviejų jos viršūnių vadinama incidentu. Viršūnės laipsnis yra į ją patenkančių briaunų skaičius. Kiekvieną grafiką plokštumoje galima pavaizduoti viršūnes atitinkančių taškų rinkiniu, kurie yra sujungti briaunas atitinkančiomis linijomis.
Grafo maršrutas yra viršūnių ir briaunų seka. Maršrutas yra uždaras (ciklinis), jei pradžios ir pabaigos viršūnės sutampa. Maršrutas yra paprasta grandinė, jei visos viršūnės ir briaunos yra skirtingos. Grafas yra sujungtas, jei kiekviena viršūnė pasiekiama iš bet kurios kitos. Viršūnės, neturinčios krintančių briaunų, vadinamos izoliuotomis.
Incidento matrica
Ryšių sąrašai
Šonkaulių sąrašas
Sujungto svertinio nenukreipto grafo grafiko gretimų matrica
Mažiausio svorio jungiamojo medžio statyba. Kruskal algoritmas Visos briaunos pašalinamos iš grafo, todėl gaunamas apimantis pografas, kuriame visos viršūnės yra izoliuotos. Kiekviena viršūnė yra patalpinta į vieną pogrupį. Kraštai rūšiuojami didinant svorį. Kraštai įtraukiami nuosekliai, didėjančia jų svorio tvarka, į besitęsiantį medį.
Skiriami 4 atvejai: 1) abi įtrauktos briaunos viršūnės priklauso pavieniams poaibiams, tada jos sujungiamos į naują, sujungtą poaibį; 2) viena iš viršūnių priklauso sujungtam poaibiui, o kita – ne, tada antrąją įtraukiame į poaibį, kuriam priklauso pirmoji; 3) abi viršūnės priklauso skirtingiems sujungtiems poaibiams, tada poaibius sujungiame; 4) Abi viršūnės priklauso tam pačiam sujungtam poaibiui, tada šią briauną neįtraukiame.
Grafo GG minimalaus svorio apimties medžio konstravimo pavyzdys Atliekami veiksmai Viršūnių aibė 1 grafikas Sukurkime apimantį pografą su izoliuotais ir viršūnėmis Gausime 5 vieno elemento poaibius: (V 1 ), (V 2) ), (V 3 ), (V 4 ), (V 5 ) 2Raskite minimalaus svorio briauną (R 15) ir pridėkite ją prie apimančio pografo Sudarome sujungtą viršūnių poaibį: (V 1,V 5). Išsaugome poaibius (V 2), (V 3), (V 4)
Veiksmai, kuriuos reikia atlikti Viršūnių rinkinys Grafikas 3 Tarp likusių raskite minimalaus svorio kraštą (R 45) ir pridėkite jį prie apimančio pografo Pridėkite viršūnę prie sujungto poaibio: (V 1, V 5, V 4 ). Išsaugome poaibius (V 2), (V 3) 4Tarp likusių randame minimalaus svorio kraštinę (R 23) ir pridedame prie apimančio pografo Sudarome naują sujungtą viršūnių poaibį: (V 2, V 3). Išsaugome pirmąjį prijungtą poaibį (V 1, V 5, V 4).
Veiksmai, kuriuos reikia atlikti Viršūnių rinkinys Grafikas 5 Tarp likusių randame minimalaus svorio kraštinę (R 25) ir pridedame prie apimančio pografo Poaibius sujungiame į vieną sujungtą poaibį (V 1,V 5, V 4, V 2, V 3). 6 Likusios briaunos neįtrauktos į grafiką, nes visos jų viršūnės jau priklauso vienai sujungtai aibei.
Veiksmai, kuriuos reikia atlikti Viršūnių rinkinys Grafikas 7 Gaunamas grafikas, kuris yra: apimantis (įtraukiamos visos viršūnės); prijungtas (visas viršūnes galima sujungti maršrutais); medis (be kilpų); turi minimalų svorį. 8Gautas apimantis medis turi minimalų svorį: R 12 +R 25 +R 15 +R 45 = =80 9 Grafo G ciklinis skaičius yra γ=m-n+1=8-5+1=4, kuris atitinka į medį neįtrauktų kraštų skaičių.
Kintamųjų deklaravimas Dvi sveikųjų skaičių penkių elementų masyvai X ir Y grafo viršūnių koordinatėms saugoti Sveikasis dvimatis masyvas R grafo kraštinių svoriams saugoti Sveikųjų skaičių kintamieji i, n ir k kilpų skaitikliams Sveikasis kintamasis S, skirtas saugoti minimalaus svorio medžio kraštų svorių suma
Atsitiktinių 5 viršūnių grafo koordinačių generavimas (kilpa per i). Kraštinių svorių skaičiavimas. Svertinio digrafo gretimumo matricos išvestis (n ir k įdėtos kilpos) Svertinio neorientuoto grafo gretumo matricos išvestis - pusė pradinės matricos elementų (pradinė reikšmė k=n+1) Programos korpusas
Įranga:
- kompiuterių klasė aprūpinta modernia technika, vaizdo projektoriumi, ekranu;
- kompiuteriai su Windows XP OS, Microsoft Office 2003 PowerPoint;
- lentos įranga (pamokos tema, nauji terminai). Dalomoji medžiaga.
Pamokos planas.
II. Naujos medžiagos pristatymas. (10 min.)
III. Medžiagos tvirtinimas. Praktinis darbas. (15-20 min.)
IV. Pamokos apibendrinimas (2 min.)
V. Namų darbai.
I. Organizacinis momentas. Žinių atnaujinimas.
Sveiki! Mūsų pamoka vadinasi „Grafikai“. Susipažinsime su „Grafų“ sąvoka, išmoksime juos pavaizduoti ir spręsti problemas šia tema.
II Naujos medžiagos pristatymas.
Pirmasis darbas apie grafų teoriją priklauso Leonhardui Euleriui (1736), nors terminą „grafas“ 1936 m. pirmą kartą įvedė vengrų matematikas Dénesas Königas. Grafikai buvo pavadinimai schemoms, sudarytoms iš taškų ir linijų atkarpų arba šiuos taškus jungiančių kreivių (grafikų pavyzdžiai pateikti 1 paveiksle).
Grafikų pagalba dažnai buvo supaprastintas įvairiose žinių srityse suformuluotų uždavinių sprendimas: automatikos, elektronikos, fizikos, chemijos ir kt.. Grafikų pagalba vaizduojamos kelių, dujotiekių, šilumos ir elektros tinklų schemos. . Grafikai padeda spręsti matematines ir ekonomines problemas.
Grafas – (iš graikų grapho – rašau) yra priemonė vizualiai pavaizduoti objekto elementus ir ryšius tarp jų. Tai nuostabūs matematiniai objektai, kurių pagalba galite išspręsti daugybę skirtingų, išoriškai nepanašių problemų.
Grafikas yra tam tikras informacijos modelis
Grafas susideda iš viršūnių arba mazgų, sujungtų lankais arba atkarpomis – briaunomis. Linija gali būti nukreipta, ty turėti rodyklę (lanką), jei nenukreipta, ji turi kraštą. Dvi viršūnės, sujungtos lanku arba briauna, vadinamos gretimomis.
Grafikų pavyzdžiai (4, 5, 6 skaidrė)
1 užduotis (7 skaidrė):
Kosminis ryšys užmegztas tarp devynių Saulės sistemos planetų. Suplanuotos raketos skrenda šiais maršrutais:
Žemė – Merkurijus; Plutonas – Venera; Žemė – Plutonas; Plutonas – Merkurijus; Merkurijus – Venera; Uranas – Neptūnas; Neptūnas – Saturnas; Saturnas – Jupiteris; Jupiteris – Marsas; Marsas – Uranas.
Ar įmanoma įprastomis raketomis skristi iš Žemės į Marsą?
Sprendimas: Nubraižykime sąlygos diagramą: planetas pavaizduosime taškais, o raketų maršrutus – linijomis.
Dabar iš karto aišku, kad iš Žemės į Marsą skristi neįmanoma.
Dvi viršūnės, sujungtos lanku arba briauna, vadinamos gretimomis. Kiekviena briauna ar lankas yra susietas su skaičiumi. Skaičius gali nurodyti atstumą tarp gyvenviečių, perėjimo iš vieno piko į kitą laiką ir kt.
2 užduotis (9 skaidrė) – sprendimas prie lentos. Masha atvyko į zoologijos sodą ir nori pamatyti kuo daugiau gyvūnų. Kuriuo keliu ji turėtų eiti? Geltona, raudona, žalia?
3 užduotis (11 skaidrės) – sprendimas prie lentos. Penkios futbolo komandos A, B, C, D, D turi sužaisti rungtynes tarpusavyje. Jau žaidė A su B, C, D; B su A, C, D. kiek rungtynių jau sužaista? Kiek laiko liko žaisti?
Grafikų pateikimas (12 skaidrė)
Grafiką galima pateikti kaip lankų sąrašą (AB; 7), grafiškai arba naudojant lentelę.
| Lankų sąrašai | Grafinė forma | Lentelinė forma | ||||||||||||||||
| (AB; 7), |  |
|
III. Sutvirtinančios medžiagos: mokinių prašoma pasiskirstyti į grupes ir atlikti užduotis. Dirbdami mažoje grupėje mokiniai aptaria modelius, remdamiesi pamokos pradžioje įgytomis teorinėmis žiniomis. Tai užtikrina medžiagos pasikartojimą ir sutvirtinimą.
2 užduotis (13 skaidrė)
IV. Pamokos santrauka
Vaikinai, kokių naujų žodžių šiandien išmokote? (Grafas, grafiko viršūnė, grafiko briaunos.)
Ką gali pavaizduoti grafo viršūnės? (Miestai; objektai, kurie yra; susiję.)
Ką reiškia grafiko kraštai (keliai, judesiai, kryptys)
Pateikite pavyzdį, kur gyvenime galime juos sutikti?
Kaip vaizduojami grafikai?
V. Namų darbai. (15 skaidrė)
Korobova Anastasija, studentė gr. 14-PGS-48D
Šiais laikais svarbu tyrinėti įvairius metodus, savybes ir nestandartinius pritaikymus. Apsvarstysime Grafo metodo taikymą mus supančioje tikrovėje.
Žodis „grafas“ matematikoje reiškia paveikslą su keliais nubrėžtais taškais, kai kurie iš jų sujungti linijomis. Visų pirma, verta pasakyti, kad grafai, apie kuriuos bus kalbama, neturi nieko bendra su praėjusių laikų aristokratais. Mūsų „grafai“ yra graikiško žodžio „grapho“ šaknys, o tai reiškia „aš rašau“. Ta pati šaknis yra žodžiuose „grafas“, „biografija“.
Pirmasis darbas apie grafų teoriją priklauso Leonhardui Euleriui ir pasirodė 1736 metais Sankt Peterburgo mokslų akademijos leidiniuose.
Aptikti skaičiai:
fizikoje – statant elektros grandines
chemijoje ir biologijoje – tiriant jų grandinių molekules
istorijoje – surašant giminės medžius (kilmes)
geografijoje – braižant žemėlapius
geometrijoje - daugiakampių, daugiakampių, erdvinių figūrų brėžiniai
ekonomikoje – sprendžiant optimalaus krovininio transporto srautų kelio parinkimo problemas (oro linijų, metro, geležinkelio schemos)
Grafų teorija naudojama matematikos olimpiadų uždaviniams spręsti. Grafikai išryškina problemos sąlygas, supaprastina sprendimą, atskleidžia problemų panašumą.
Šiais laikais bet kurioje mokslo ir technologijų šakoje susiduri su grafikais.
Parsisiųsti:
Peržiūra:
Norėdami naudoti pristatymų peržiūras, susikurkite „Google“ paskyrą ir prisijunkite prie jos: https://accounts.google.com
Skaidrių antraštės:
Pristatymą matematikos tema: „Grafikai“ užbaigė 14-PGS-48D grupės mokinė Anastasija Korobova
Grafikas yra figūra, susidedanti iš taškų ir juos jungiančių linijų. Linijos vadinamos grafo briaunomis, o taškai – viršūnėmis. Viršūnės, iš kurių atsiranda lyginis briaunų skaičius, vadinamos lyginėmis, o nelyginis skaičius – nelyginėmis. Grafų pavyzdžiai Grafų teorija
Leonhardas Euleris (1707 m. balandžio 4 d. Bazelis, Šveicarija – 1783 m. rugsėjo 7 d. Sankt Peterburgas, Rusijos imperija) – šveicarų, vokiečių ir rusų matematikas, daug prisidėjęs plėtojant matematiką, taip pat mechaniką, fiziką, astronomiją. ir nemažai taikomųjų mokslų. Euleris yra daugiau nei 800 darbų apie matematinę analizę, diferencialinę geometriją, skaičių teoriją, apytikslius skaičiavimus, dangaus mechaniką, matematinę fiziką, optiką, balistiką, laivų statybą, muzikos teoriją ir kt. autorius.
Figūra (grafikas), kurią galima nupiešti nepakeliant pieštuko nuo popieriaus, vadinama vienareikšmiu. Šablonas 1. Grafą, kuriame yra tik dvi nelyginės viršūnės, galima nubraižyti nepakeliant pieštuko nuo popieriaus, o judėjimas turi prasidėti nuo vienos iš šių nelyginių viršūnių ir baigtis antroje iš jų. (A pav.) 2 modelis. Grafas, turintis daugiau nei dvi nelygines viršūnes, negali būti nubrėžtas „vienu brūkšniu“ (B pav.) Eulerio grafikai B A
Raštas 3. Jei visos grafiko viršūnės yra lygios, galite nubrėžti šį grafiką nepakeldami pieštuko nuo popieriaus, judėdami išilgai kiekvieno krašto tik vieną kartą. Judėjimas gali prasidėti nuo bet kurios viršūnės ir baigtis toje pačioje viršūnėje.
Tarp Karaliaučiaus gyventojų nuo seno buvo paplitusi tokia mįslė: kaip pereiti visus tiltus (per Pregolya upę), neperėjus nė vieno iš jų du kartus? Daugelis bandė išspręsti šią problemą tiek teoriškai, tiek praktiškai, pasivaikščiojimų metu.. Karaliaučiaus tiltų problema.
Tai grafikas, kuriame kai kurios briaunos gali būti nukreiptos, o kai kurios briaunos gali būti nenukreiptos. Mišrus grafikas
Svertinis grafikas 1 2 4 2 3 A B C D E
Medis yra bet koks sujungtas grafikas, neturintis ciklų. Medžiai Medžiai
Tai (daugelis) grafikas, kurio briaunoms priskirta kryptis. Nukreiptos briaunos dar vadinamos lankais. Nukreiptas grafikas
Aptikti skaičiai:
Grafų teorija naudojama matematikos olimpiadų uždaviniams spręsti. Grafikai išryškina problemos sąlygas, supaprastina sprendimą, atskleidžia problemų panašumą. Šiais laikais bet kurioje mokslo ir technologijų šakoje susiduri su grafikais.
Ačiū už dėmesį!
Norėdami peržiūrėti pristatymą su paveikslėliais, dizainu ir skaidrėmis, atsisiųskite failą ir atidarykite jį „PowerPoint“. kompiuteryje.
Pristatymo skaidrių tekstinis turinys: Grafai ir jų taikymas sprendžiant uždavinius Turinys Kas yra grafas Grafo savybės Grafų atsiradimo istorija Karaliaučiaus tiltų problema Grafų taikymas Išvados Kas yra grafikas Matematikoje grafo apibrėžimas pateikiamas taip: A. grafas – tai netuščia taškų ir atkarpų aibė, kurių abu galai priklauso tam tikrai taškų aibei.Taškai vadinami grafo viršūnėmis, o jungiamosios linijos – briaunomis. Grafo kraštai Grafo viršūnės Kitas Kas yra grafas Kraštinių, išeinančių iš grafo viršūnės, skaičius vadinamas viršūnės laipsniu. Nelyginio laipsnio grafiko viršūnė vadinama nelygine, o lyginio laipsnio viršūnė vadinama lygine. Nelyginio laipsnio Lyginio laipsnio turinys Grafų savybės Grafe visų jo viršūnių laipsnių suma yra lyginis skaičius, lygus dvigubam grafo briaunų skaičiui Bet kurio grafo nelyginių viršūnių skaičius yra lyginis. Grafas su n viršūnių, kur n≥2, visada yra dvi viršūnės su vienodais laipsniais . Grafų savybės Jei grafe su n viršūnių (n>2) lygiai dvi viršūnės turi tą patį laipsnį, tai šiame grafe visada yra arba tiksliai viena 0 laipsnio viršūnė, arba lygiai viena n-1 laipsnio viršūnė. grafas turi n viršūnių, tada briaunų skaičius bus lygus n(n-1)/2. Grafo ypatybės Pilnas grafas Nepilnas grafikas Grafo savybės Nukreiptas grafas Nenukreiptas grafas Izomorfiniai grafikai Grafų istorija Terminas „grafas“ pirmą kartą pasirodė vengrų matematiko D. Koenigo knygoje 1936 m., nors pradinės svarbiausios teoremos apie grafikus išeina. atgal pas L. Eulerį. Tolesnė grafų atsiradimo istorija Grafų teorijos, kaip matematinio mokslo, pagrindus 1736 m. padėjo Leonhardas Euleris, svarstydamas Karaliaučiaus tiltų problemą. Šiandien ši užduotis tapo klasikine. turinys Problema dėl Karaliaučiaus tiltų Buvęs Karaliaučius (dabar Kaliningradas) yra prie Pregelio upės. Miesto viduje upė skalauja dvi salas. Nuo krantų į salas buvo statomi tiltai. Senųjų tiltų neišliko, tačiau išlikęs miesto žemėlapis, kuriame jie pavaizduoti. Toliau Problema dėl Karaliaučiaus tiltų Tarp Karaliaučiaus gyventojų buvo paplitusi tokia problema: ar įmanoma pereiti visus tiltus ir grįžti į pradinį tašką, aplankant kiekvieną tiltą tik vieną kartą? Tolesnė Karaliaučiaus tiltų problema Neįmanoma eiti per Karaliaučiaus tiltus laikantis nurodytų sąlygų. Ėjimas per visus tiltus, su sąlyga, kad kiekvieną kartą reikia aplankyti ir grįžti į kelionės pradžios tašką, grafų teorijos kalba atrodo kaip užduotis pavaizduoti grafiką „vienu brūkšniu“. toliau Karaliaučiaus tiltų problema Tačiau, kadangi grafas šiame paveiksle turi keturias nelygines viršūnes, tokio grafo nubraižyti „vienu brūkšniu“ neįmanoma. turinys Eulerio grafikas Grafikas, kurį galima nubraižyti nepakeliant pieštuko nuo popieriaus, vadinamas Eilerio grafiku. Spręsdamas Karaliaučiaus tiltų uždavinį, Euleris suformulavo grafo savybes: Nelyginių grafo viršūnių (viršūnių, į kurias veda nelyginis briaunų skaičius) skaičius turi būti lyginis. Negali būti grafiko, kuriame būtų nelyginis skaičius nelyginių viršūnių. Jei visos grafiko viršūnės yra lyginės, galite nubrėžti grafiką nepakeldami pieštuko nuo popieriaus, o pradėti nuo bet kurios grafiko viršūnės ir baigti tai toje pačioje viršūnėje.. Grafas, turintis daugiau nei dvi nelygines viršūnes, negali būti nubraižytas vienu brūkštelėjimu. tolimesnis Eulerio grafikas Jei visos grafiko viršūnės yra lygios, tai šį grafiką galite nubraižyti nepakeldami pieštuko nuo popieriaus („vienu potėpiu“), eidami išilgai kiekvieno krašto tik vieną kartą. Judėjimas gali prasidėti nuo bet kurios viršūnės ir baigtis toje pačioje viršūnėje. toliau Eulerio grafikas Grafą, kuriame yra tik dvi nelyginės viršūnės, galima nubrėžti nepakeliant pieštuko nuo popieriaus, o judėjimas turi prasidėti nuo vienos iš šių nelyginių viršūnių ir baigtis antroje iš jų. tolimesnis Eulerio grafikas Grafas, turintis daugiau nei dvi nelygines viršūnes, negali būti nubraižytas „vienu brūkšniu“. ? Grafikų naudojimas Naudojant grafikus, matematinių uždavinių, galvosūkių ir išradingumo uždavinių sprendimas yra supaprastintas. toliau Grafų taikymas Uždavinys: Arkadijus, Borisas. Vladimiras, Grigorijus ir Dmitrijus susitikę paspaudė vienas kitam ranką (kiekvienas vieną kartą paspaudė vienas kitam ranką). Kiek rankų paspaudimų buvo padaryta? toliau Grafikų taikymas Sprendimas: A D C B D 1 2 3 4 5 6 7 8 9 10 toliau Grafikų taikymas Valstybėje oro linijų sistema suprojektuota taip, kad bet kuris miestas oro linijų būtų sujungtas ne daugiau kaip su trimis kitais, o nuo iš bet kurio miesto į bet kurį kitą Keliauti galite atlikę ne daugiau kaip vieną pakeitimą. Koks didžiausias miestų skaičius gali būti šioje valstijoje? Grafikų taikymas Tebūnie tam tikras miestas A. Iš jo galima pasiekti ne daugiau kaip tris miestus, o iš kiekvieno iš jų ne daugiau kaip du (neskaičiuojant A). Tuomet bendras miestų skaičius yra ne daugiau 1+3+6=10. Tai reiškia, kad miestų iš viso yra ne daugiau kaip 10. Paveikslėlyje pateiktas pavyzdys rodo oro linijų egzistavimą. Grafikų taikymas Yra 3x3 šachmatų lenta, viršutiniuose dviejuose kampuose yra du juodi riteriai, apatiniuose - du balti (nuotrauka žemiau). Per 16 ėjimų vietoj juodųjų pastatykite baltuosius riterius, o vietoj baltųjų – juoduosius ir įrodykite, kad mažiau judesių to padaryti neįmanoma. Grafų taikymas Išplėtę galimų riterių judesių grafiką į apskritimą, matome, kad pradžioje riteriai stovėjo taip, kaip paveikslėlyje žemiau: Išvados Grafikai yra nuostabūs matematiniai objektai, kurių pagalba galima spręsti matematinius, ekonominius ir loginės problemos. Taip pat galite spręsti įvairius galvosūkius ir supaprastinti fizikos, chemijos, elektronikos ir automatikos uždavinių sąlygas. Grafikai naudojami kuriant žemėlapius ir šeimos medžius. Yra net specialus matematikos skyrius, vadinamas „Grafų teorija“. turinys
Prikabinti failai
Įkeliama...
