elementi teorii grafov

PPT 39 pages 955.9 KB Free download

39 pages

FaylHub.uz

Download via Telegram

Size 955.9 KB

File type PPT

Pages 39

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 39

slayd 1 elementi teorii grafov soderjanie 1. osnovnie ponyatiya teorii grafov 2. stepen vershini vvedenie 5. orientirovannie grafi 6. izomorfizm grafov 7. ploskie grafi 8. operatsii nad grafami 9. sposobi zadaniya grafov 3. marshruti, tsepi, tsikli 10. nekotorie tipi grafov 10. nekotorie tipi grafov 11. nekotorie zadachi teorii grafov grafov vvedenie teoriya grafov v kachestve distsiplini mojet rassmatrivatsya kak razdel diskretnoy matematiki, issleduyushiy svoystva konechnix mnojestv s zadannimi otnosheniyami mejdu ix elementami (izuchenie ob'ektov). kak prikladnaya distsiplina teoriya grafov pozvolyaet opisivat i issledovat mnogie texnicheskie, ekonomicheskie, biologicheskie i sotsialnie sistemi. osobenno shirokoe primenenie teorii grafov v takix oblastyax prikladnoy matematiki, kak programmirovanie, teoriya konechnix avtomatov, v reshenii veroyatnostnix i kombinatornix zadach. osnovopolojniki rodilas teoriya grafov v sankt-peterburge. ee sozdatelem yavlyaetsya l. eyler, kotoriy v 1736 godu opublikoval reshenie zadachi o kenigsbergskix mostax. zadacha o kenigsbergskix mostax. v prusskom gorodke kenigsberg na reke pregel sem mostov. mojno li nayti marshrut progulki, …

2 / 39

ov, nazivaemiy derevyami. jordan (1869 god), nezavisimo ot kelli, vvel i izuchal derevya kak chisto matematicheskie ob'ekti, sovershenno ne podozrevaya o znachenii svoego otkritiya dlya sovremennoy ximicheskoy nauki. d.kenig l.v.kantorovich nachalo burnogo razvitiya i prakticheskogo primeneniya teorii grafov bilo polojeno vengerskim matematikom d. kenigom, kotoriy opublikoval v 1936 g. monografiyu «teoriya konechnix i beskonechnix grafov». rossiyskiy akademik l. v. kantorovich razrabotal metod resheniya transportnix zadach dlya ix setevoy postanovki. 1. osnovnie ponyatiya teorii grafov graf predstavlyaet soboy nepustoe konechnoe mnojestvo vershin v i reber e, oba kontsa kotorix prinadlejat mnojestvu v. oboznachat graf budem pri izobrajenii grafov na risunkax ili sxemax rebra mogut bit pryamolineynimi ili krivolineynimi; dlini reber i raspolojenie vershin proizvolni. vershini, kotorie ne prinadlejat ni odnomu rebru, nazivayut izolirovannimi. oboznachat vershini budem t. e. v={ } pust - vershini, - soedinyayushie ix rebro. togda vershina i rebro intsidentni. vershina i rebro e takje intsidentni. dva rebra (vershini …

3 / 39

rafa. chislo nechetnix vershin lyubogo grafa chetno. vo vsyakom grafe s n vershinami, gde n ≥ 2 vsegda naydutsya, po menshey mere, dve vershini s odinakovimi stepenyami. esli v grafe s n vershinami (n ≥ 2) v tochnosti dve vershini imeyut odinakovuyu stepen, to v etom grafe vsegda naydetsya libo v tochnosti odna vershina stepeni 0, libo v tochnosti odna vershina stepeni n-1. svoystva stepeni vershini marshrutom v grafe nazivaetsya chereduyushayasya posledovatelnost vershin i reber, v kotoroy lyubie dva sosednix elementa intsidentni: esli to marshrut zamknut, v protivnom sluchae otkrit. esli vse rebra razlichni, to marshrut nazivaetsya tsepyu. esli vse vershini razlichni, to marshrut nazivaetsya prostoy tsepyu. v tsepi vershini nazivayutsya kontsami tsepi, t. e. tsep kontsami soedinyaet vershini . tsep, soedinyayushaya vershini , oboznachaetsya ( ). zamknutaya tsep nazivaetsya tsiklom, zamknutaya prostaya – prostim tsiklom, chislo tsiklov oboznachaetsya z(g). graf bez tsiklov – atsiklicheskiy. dlinnoy marshruta nazivaetsya kolichestvo reber …

4 / 39

lkoy mejdu vershinami. graf u kotorogo vse rebra orientirovani – orientirovanniy. orientirovannoe rebro neorientirovannoe rebro odna i ta je vershina orientirovannogo grafa mojet slujit nachalom dlya odnix reber i kontsom dlya drugix, poetomu razlichayut dve stepeni vershini: stepenyu vixoda vershini orgrafa – chislo vixodyashix iz vershini reber; stepenyu vxoda vershini orgrafa – chislo vxodyashix v vershinu reber. ris 5.1 ris 5.2 5. orientirovannie grafi v orgrafax v zavisimosti ot sochetaniya stepeney vxoda i vixoda dlya dannoy vershini rassmatrivayutsya tri sluchaya: izolirovannoy vershinoy nazivaetsya vershina u kotoroy stepen vxoda i stepen vixoda ravni 0; istochnikom nazivaetsya vershina, stepen vixoda kotoroy polojitelna, a stepen vxoda ravna 0; stokom nazivaetsya vershina, stepen vxoda kotoroy polojitelna, a stepen vixoda ravna 0. putem v orientirovannom grafe nazivaetsya posledovatelnost orientirovannix reber. prostim putem v orientirovannom grafe nazivaetsya put, v kotorom ni odna vershina ne soderjitsya bolee odnogo raza (ris 5.3). na ris 5.4 izobrajen put, ne …

5 / 39

ystvami refleksivnosti, simmetrichnosti, tranzitivnosti. dlya togo chtobi graf bil izomorfen grafu , neobxodima takaya podstanovka, kotoraya bi ustanovila vzaimno-odnoznachnoe sootvetstvie mejdu vershinami grafa i ix rebrami. pri zamene grafa lyubim emu izomorfnim vse svoystva grafa soxranyayutsya. strogo govorya, grafi, otlichayushiesya tolko numeratsiey vershin, yavlyayutsya izomorfnimi. 6. izomorfizm grafov dva grafa nazivayutsya izomorfnimi, esli mejdu mnojestvami ix vershin sushestvuet biektivnoe (vzaimno-odnoznachnoe) sootvetstvie, takoe, chto vershini soedineni rebrami v odnom iz grafov v tom i tolko v tom sluchae, kogda sootvetstvuyushie im vershini soedineni v drugom grafe. algoritm raspoznavaniya dvux grafov i podschitivaem chislo vershin kajdogo grafa (chislo vershin doljno sovpadat, v protivnom sluchae grafi neizomorfnie). vipisivaem vse elementi oboix grafov v estestvennoy uporyadochennosti i opredelyaem pari i dlya kajdogo ele-menta, gde - chislo isxodov dlya kajdoy vershini grafov i , a - chislo zaxodov dlya sootvetstvuyushix grafov. dlya kajdogo elementa x grafa ishem takoy element u grafa , chto vipolnyaetsya uslovie: …

Want to read more?

Download all 39 pages for free via Telegram.

Download full file

About "elementi teorii grafov"

slayd 1 elementi teorii grafov soderjanie 1. osnovnie ponyatiya teorii grafov 2. stepen vershini vvedenie 5. orientirovannie grafi 6. izomorfizm grafov 7. ploskie grafi 8. operatsii nad grafami 9. sposobi zadaniya grafov 3. marshruti, tsepi, tsikli 10. nekotorie tipi grafov 10. nekotorie tipi grafov 11. nekotorie zadachi teorii grafov grafov vvedenie teoriya grafov v kachestve distsiplini mojet rassmatrivatsya kak razdel diskretnoy matematiki, issleduyushiy svoystva konechnix mnojestv s zadannimi otnosheniyami mejdu ix elementami (izuchenie ob'ektov). kak prikladnaya distsiplina teoriya grafov pozvolyaet opisivat i issledovat mnogie texnicheskie, ekonomicheskie, biologicheskie i sotsialnie sistemi. osobenno shirokoe primenenie teorii grafov v takix oblastyax prikladnoy matematiki, kak prog...

This file contains 39 pages in PPT format (955.9 KB). To download "elementi teorii grafov", click the Telegram button on the left.

Tags: elementi teorii grafov PPT 39 pages Free download Telegram