Тарихтағы графикалық түсінік. Графикалық теория

Леонард Эйлер графтар теориясының негізін салушы болып саналады. 1736 жылы ол өзінің хаттарының бірінде жеті Кенигсберг көпірі мәселесінің шешімін тұжырымдайды және ұсынады, ол кейінірек олардың бірі болды. классикалық мәселелерграфикалық теория.

Графтар теориясындағы алғашқы есептер математикалық рекреациялық есептер мен басқатырғыштарды шешуге қатысты болды. Міне, Эйлердің 1736 жылғы 13 наурыздағы хатынан үзіндіні қайталау: «Маған Кенигсберг қаласында орналасқан және оның үстінен 7 көпір өтетін өзенмен қоршалған арал туралы мәселе берілді. Мәселе біреу оларды үздіксіз айналып өтіп, әр көпірден бір-ақ рет өте алады ма. Содан кейін маған мұны әлі ешкім жасай алмағанын хабарлады, бірақ бұл мүмкін емес екенін ешкім дәлелдеген жоқ. Бұл сұрақ тривиальды болғанымен, маған назар аударуға тұрарлық болып көрінді, өйткені оны шешу үшін геометрия да, алгебра да, комбинаторлық өнер де жеткіліксіз. Көп ойланғаннан кейін мен толық сенімді дәлелге негізделген оңай ережені таптым, оның көмегімен осы тектес барлық есептер бойынша кез келген сан және кез келген сан арқылы мұндай айналма жолды жасауға болатынын бірден анықтауға болады. көпірлер кез келген жолмен орналасқан немесе жоқ». Кенигсберг көпірлерін схемалық түрде келесідей бейнелеуге болады:

Эйлер ережесі:

1. Тақ дәрежелі төбелері жоқ графикте графтың кез келген төбесінен басталып, барлық шеттерінің (және әрбір жиегі дәл бір рет кесілген) өтуі болады.

2. Екі және тек екі төбесі тақ градустары бар графикте бір төбесінен басталатын өту бар. тақ дәрежежәне екіншісімен аяқталады.

3. Тақ дәрежелі екі төбеден көп графта мұндай өту болмайды.

Графиктер бойымен саяхаттауға қатысты мәселенің тағы бір түрі бар. Біз барлық шыңдардан өтетін жолды табу қажет және әрқайсысы арқылы бір реттен көп емес есептер туралы айтып отырмыз. Әрбір төбеден бір-ақ рет өтетін цикл Гамильтон сызығы деп аталады (мұндай сызықтарды алғаш зерттеген өткен ғасырдағы атақты ирланд математигі Уильям Роуэн Гамильтонның атымен). Өкінішке орай, жалпы критерий әлі табылған жоқ, оның көмегімен берілген графтың Гамильтондық екенін анықтауға болады, егер солай болса, онда барлық Гамильтон сызықтарын табыңыз.

19 ғасырдың ортасында құрастырылған. Төрт түс мәселесі де қызықты мәселе сияқты көрінеді, бірақ оны шешуге тырысу теориялық және қолданылатын мән. Төрт түсті есеп келесідей тұжырымдалған: «Кез келген жазық картаның аумағын төрт түспен бояуға болады, осылайша кез келген екі көрші аумақ әртүрлі түстермен боялады?» Жауаптың дұрыс екендігі туралы гипотеза 19 ғасырдың ортасында тұжырымдалған. 1890 жылы әлсіз мәлімдеме дәлелденді, атап айтқанда, кез келген жалпақ картаны бес түске бояуға болады. Кез келген жазық картаны оның қос жазық графигімен байланыстыра отырып, есептің графиктер бойынша эквивалентті тұжырымын аламыз: Кез келген жазық графиктің хроматикалық саны төрттен кем немесе оған тең екені рас па? Мәселені шешудің көптеген әрекеттері графтар теориясының бірқатар салаларының дамуына әсер етті. 1976 жылы компьютерді қолдану арқылы мәселенің оң шешімі жарияланды.

Ұзақ уақыт бойы шешуге ерекше төзімді және басқатырғыштарды ұнататын тағы бір ескі топологиялық мәселе «электр, газ және сумен қамтамасыз ету мәселесі» ретінде белгілі. 1917 жылы Генри Э. Дудени оған осы тұжырымды берді. Суретте көрсетілген үш үйдің әрқайсысына газ, электр және су тартылуы керек.

Графикалық теория. 1

Графтар теориясының пайда болу тарихы. 1

Эйлер ережесі. 1

Әдебиет

1. Белов графикалық теориясы, Мәскеу, «Ғылым», 1968.

2. Жаңа педагогикалық және ақпараттық технологияларЕ.С.Полат , Мәскеу, «Академия» 1999

3. Кузнецов О.П., Адельсон-Вельский Г.М. Инженерге арналған дискретті математика. – М.: Энергоатимиздат, 1988.

4. Кук Д., Базе Г. Компьютерлік математика. – М.: Ғылым, 1990.

5. Нефедов В.Н., Осипова В.А. Дискретті математика курсы. – М.: МАИ баспасы, 1992.

6. Кенді О. График теориясы. – М.: Ғылым, 1980.

7. Исмагилов Р.С., Калинкин А.В. Курстағы практикалық сабақтарға арналған материалдар: Дискретті математика

неміс Граф), дворяндық атақ. Ресейге Петр I енгізген (Б.П. Шереметев 1706 жылы алғаш рет алған). 19 ғасырдың аяғында. 300-ден астам отбасы есепке алынды. Бүкілресейлік Орталық Атқару Комитеті мен Халық Комиссарлар Кеңесінің 1917 жылғы 11 қарашадағы Декретімен таратылды.

Тамаша анықтама

Толық емес анықтама ↓

График

Антон (Граф, Антон) 1736 ж., Винтертур – 1813 ж., Дрезден. Неміс суретшісі. Ол 1753-1756 жылдары Винтертурде И.В.Шелленбергтен, кейін Аугсбургте И.Я.Гайдпен бірге оқыды. Регенсбург, Винтертур, Аугсбург, Мюнхен, Цюрих қалаларында портрет суретшісі болып жұмыс істеді. 1766 жылдан - Дрездендегі сот суретшісі. 1789 жылдан - Дрезден өнер академиясының профессоры. Берлин, Вена, Мюнхен өнер академияларының мүшесі. Германия мен Швейцарияда көп саяхаттаған. Ол портреттік суретші болған, сонымен қатар пейзаждарды салған, миниатюрамен айналысқан. Суретшінің алғашқы туындылары салтанатты барокко портретінің дәстүрінде орындалды. Пруссия ханзадасы Фредерик (1777-1778), Пруссия ханшайымы Фредерика (1787), Пруссия королі Фредерик Вильям II (1788) портреттерінде Пруссия король сарайының асыл тұлғаларының бейнелері салтанаттылық пен өкілдікке толы. , барлығы - Берлин, Шарлоттенбург). Күшті хиароскюро және жылы түс схемасы жас суретшінің Рембрандт стиліне деген құмарлығын көрсетеді. 1780-1790 жылдары граф көбінесе пейзаж фонында үлгілерді бояды, бұл оның портреттеріндегі шиеленісті және статикалық фигураларды біршама жұмсартты ( Генри VIII, 1804, Германия, жеке коллекция; I. F. von Tilman, Нюрнберг, неміс ұлты. мұражай). Дәуірдің неоклассикалық талғамының рухында ол пейзажда ежелгі әсемдік ретінде бейнеленгендерді бейнелейді (Фредерика Хиллендорф, 1803, Германия, жеке коллекция). Суретшіге жақын адамдардың портреттері олардың ішкі күйін жеткізуде тереңірек: Суретші К.К.Лунвиг (1808, Гамбург, Кунстхалле), лирикалық әйел бейнелері - Луиза Элизабет Фанк (1790, Лейпциг, мұражай) бейнелеу өнері), Кэролайн Сюзанна Граф (1805, Гамбург, Кунстхалле). Нәзік жарық пен көлеңкелі модельдеу Граф кескіндеріне тән фигуралардың айқын пластикасын көрсетеді. Фигураларды қоршап тұрған әуе сфумато 18 ғасырдағы ағылшын портретінің техникасын зерттеу туралы куәландырады. Ағарту дәуірінің көрнекті қайраткерлерінің портреттері – С.Гесснер (1765-1766, Цюрих, Кунстхалле), Г.Э.Лессинг (1771, Лейпциг, университет кітапханасы), К.М.Виланд (1794, Веймар, Гете мұражайы), И.Г.Сульцер (17,17,17) Kunsthalle) - суретші жасаған ең маңызды нәрсе. Суретшінің қайын атасы, немістің атақты философы, эстетикасы және математигі И.Г.Сульцер мен швейцар ақыны, «Идиллер» (1756) поэзиялық жинағының авторы С.Геснердің портреттерінде граф барокко сызбасын пайдаланады. үзілген қозғалыс кезіндегі модельдерді бейнелейтін портрет. Ағартушылық дәуірінің нағыз суреткері граф ұлттың мәдени мұрасына айналған тұлғалардың рухани жан-дүниесін, нұрлы санасын ашуға ұмтылады. Портреттер де кейінгі басқа да бірқатар жұмыстар сияқты күңгірт фонда салынған (Х. И. Медем, 1796; Г. Л. Гогель, 1796, екеуі де – Петербург, Мемлекеттік Эрмитаж мұражайы). Суретшінің автопортреттеріне де образды психологиялық тұрғыдан тереңдетуге деген қызығушылық тән. 1765 (Нью-Йорк, Тарихи қоғам) және 1766 (Дрезден, Сурет галереясы) үзілген қозғалыс мотиві композициялық шешімге белгілі бір дәстүрлілік әкеледі. Кейінгі туындылар (1794-1795, Дрезден, Көркемсурет галереясы; 1808, Винтертур, Кунстхалле) шығармалары 18 ғасырдағы неміс мәдениетінің көптеген маңызды құбылыстарын белгілеп, кейінгі ғасырдың реалистік бейнелеу дәстүрлерін қалаған суретші бейнесін жасайды. IN кеш кезеңсуретші өмірден сурет салуды, пленэрге деген қызығушылығын және «көңіл-күй пейзажы» мәселесін дамытуды сипаттайтын бірқатар пейзаждарды салды (Дрезденнің айналасына шолу, 1800; Таңертең, шамамен 1800; Түс, шамамен 1800; Кешке, шамамен 1800, барлығы - Дрезден, Көркемсурет галереясы).

ВЛАДИМИР МЕМЛЕКЕТТІК ПЕДАГОГИКАЛЫҚ УНИВЕРСИТЕТІ

АНСТРАТ

«ГРАФ ТЕОРИЯСЫ»

Орындаған:

Зудина Т.В.

Владимир 2001 ж

1. Кіріспе

2. Графтар теориясының пайда болу тарихы

3. Графтар теориясының негізгі анықтамалары

4. Графтар теориясының негізгі теоремалары

5. Графтар теориясын қолдану бойынша есептер

6. Графтар теориясын мектеп математика курсында қолдану

7. Графиктер теориясын ғылым мен техниканың әртүрлі салаларында қолдану

8. Графтар теориясының соңғы жетістіктері

§1. ГРАФИЯ ТЕОРИЯСЫНЫҢ ПАЙДА БОЛУ ТАРИХЫ.

Графтар теориясының негізін салушы математик Леонгард Эйлер (1707-1783) болып саналады. Бұл теорияның тарихын ұлы ғалымның хат-хабарлары арқылы білуге ​​болады. Мұнда Эйлердің 1736 жылы 13 наурызда Санкт-Петербургтен жіберілген итальяндық математик және инженер Маринониге жазған хатынан алынған латын мәтінінің аудармасы берілген [қараңыз. 41-42 б.]:

"Кезінде маған Кенигсберг қаласында орналасқан және жеті көпір лақтырылған өзенмен қоршалған арал туралы мәселе қойылды. Мәселе, кез келген адам оларды үздіксіз айналып өтіп, әр көпір арқылы бір-ақ рет өте алады ма? Сосын мен болдым. мұны әлі ешкім жасай алмағанын, бірақ бұл мүмкін емес екенін ешкім дәлелдемегенін хабарлады.Бұл сұрақ тривиальды болғанымен, маған назар аударуға тұрарлық, өйткені геометрия да, алгебра да, комбинаторлық өнер де жоқ. оны шешуге жеткілікті... Көп ойланып, мен толық сенімді дәлелге негізделген жеңіл ережені таптым, оның көмегімен осы тектес мәселелердің барлығында кез келген жолмен мұндай айналма жолды жасауға болатынын бірден анықтауға болады. кез келген жолмен орналасқан немесе жоқ көпірлердің саны.оларды келесі суретте көрсетуге болады[1-сурет] , оның үстіне А аралды білдіреді және Б , C және D - материктің бір-бірінен өзен тармақтарымен бөлінген бөліктері. Жеті көпір әріптермен белгіленген а , б , в , г , e , f , g ".

(СУРЕТ 1.1)

Осы тектес мәселелерді шешудің әдісі туралы Эйлер жазды [қараңыз. 102-104 б.]:

«Бұл шешімнің өз табиғаты бойынша математикаға қатысы жоқ сияқты, мен неге бұл шешімді кез келген адамнан емес, математиктен күту керек екенін түсінбеймін, өйткені бұл шешім тек ақыл-оймен расталады, және бұл шешімнің мағынасы жоқ. Бұл шешімді табу үшін математикаға тән кез келген заңдарды тарту керек. Сонымен, математикаға өте аз қатысы бар сұрақтарды басқаларға қарағанда математиктер шешеді деп қалай шығатынын білмеймін».

Сонда Кенигсберг көпірлерін осы көпірлердің әрқайсысынан бір-ақ рет өту арқылы айналып өтуге болады ма? Жауапты табу үшін Эйлердің Маринониге жазған хатын жалғастырайық:

"Мәселе осы жеті көпірдің барлығын айналып өтіп, әрқайсысынан бір-ақ рет өтуге бола ма, жоқ па, соны анықтау керек. Менің ережем бұл сұрақтың келесі шешіміне әкеледі. Ең алдымен, ол жерде қанша аумақты қарастыру керек. сумен бөлінген - осындай , көпірден басқа бірінен екіншісіне өтуі жоқ. Бұл мысалда осындай төрт бөлім бар - А , Б , C , D . Ажырататын келесі нәрсе - бұл жеке учаскелерге апаратын көпірлер саны жұп немесе тақ. Сонымен, біздің жағдайда бес көпір А бөліміне апарады, ал қалғандарына үш көпір апарады, яғни жеке учаскелерге апаратын көпірлердің саны тақ және мәселені шешу үшін осының өзі жеткілікті. Мұны анықтағаннан кейін біз келесі ережені қолданамыз: егер әрбір жеке учаскеге апаратын көпірлердің саны жұп болса, онда қарастырылып отырған айналма жол мүмкін болар еді және сонымен бірге бұл айналма жолды кез келген учаскеден бастауға болады. . Егер осы сандардың екеуі тақ болса, тек біреуі ғана тақ болуы мүмкін емес болса, онда да көшу белгіленгендей орын алуы мүмкін, бірақ тек тізбектің басы тақ сан әкелетін екі бөлімнің бірінен алынуы керек. көпірлер. Егер, сайып келгенде, көпірлердің тақ саны апаратын екіден астам учаскесі болса, онда мұндай қозғалыс әдетте мүмкін емес ... егер мұнда басқа, неғұрлым күрделі мәселелер туындаса, бұл әдіс одан да көп пайда әкелуі мүмкін және қажет. назардан тыс қалмаңыз».

Жоғарыдағы ереженің негіздемесін сол жылдың 3 сәуірінде Л.Эйлердің досы Эхлерге жазған хатынан табуға болады. Төменде осы хаттан үзіндіні қайталаймыз.

Математик егер өзеннің айырында көпірлердің тақ саны апаратын екіден артық учаске болмаса, көшу мүмкін деп жазды. Мұны елестетуді жеңілдету үшін біз суреттегі бұрыннан өтіп кеткен көпірлерді өшіреміз. Тексеру оңай, егер біз Эйлер ережелеріне сәйкес қозғала бастасақ, бір көпірден өтіп, оны өшірсек, онда суретте қайтадан көпірлердің тақ саны апаратын екі аймақтан аспайтын және егер бар болса, бөлім көрсетіледі. тақ сан көпірлері бар аймақтар, біз олардың бірінде орналасамыз. Осылай жүре берсек, барлық көпірлерден бір рет өтеміз.

Кенигсберг қаласының көпірлерінің тарихы заманауи жалғасы бар. Мысалға, Н.Я. редакциясының математикадан мектеп оқулығын ашайық. Виленкина алтыншы сыныпқа. Онда 98-беттегі зейінділік пен интеллектті дамыту айдарымен бір кездері Эйлер шешкен мәселеге тікелей қатысы бар мәселені табамыз.

№ 569 есеп. Көлде 1.2 суретте көрсетілгендей бір-бірімен байланысқан жеті арал бар. Әр көпірден бір рет өту үшін қайық саяхатшыларды қай аралға апаруы керек? Неліктен саяхатшыларды аралға тасымалдауға болмайды? А ?

(СУРЕТ 1.2)

Шешім.Бұл мәселе Кенигсберг көпірлерінің мәселесіне ұқсас болғандықтан, оны шешуде Эйлер ережесін де қолданамыз. Нәтижесінде біз келесі жауап аламыз: қайық саяхатшыларды аралға жеткізуі керек Енемесе Фсондықтан олар әр көпірден бір рет өте алады. Сол Эйлер ережесінен, егер ол аралдан басталса, қажетті айналма жолдың мүмкін еместігі шығады А .

Қорытындылай келе, Кенигсберг көпірлері мәселесі және соған ұқсас есептер оларды зерттеу әдістерінің жиынтығымен бірге граф теориясы деп аталатын практикалық тұрғыдан математиканың өте маңызды саласын құрайтынын атап өтеміз. Графиктер туралы алғашқы еңбек Л.Эйлерге тиесілі және 1736 жылы пайда болды. Одан кейін графтармен Кениг (1774-1833), Гамильтон (1805-1865), қазіргі математиктер К.Берге, О.Оре, А.Зыковтар жұмыс істеді.

§2. ГРАФИК ТЕОРИЯСЫНЫҢ НЕГІЗГІ ТЕОРЕМАЛАРЫ

График теориясы, жоғарыда айтылғандай, математиктердің күш-жігерімен жасалған математикалық пән, сондықтан оны ұсыну қажетті қатаң анықтамаларды қамтиды. Сонымен, осы теорияның негізгі ұғымдарын ұйымдасқан түрде енгізуге көшейік.

Анықтама 2.01. Санаудеп аталатын нүктелердің шектеулі санының жиынтығы шыңдарграфик және осы шыңдардың кейбірін қосатын жұптық сызықтар деп аталады қабырғаларнемесе доғаларграфик.

Бұл анықтаманы басқаша тұжырымдауға болады: санаунүктелердің бос емес жиыны деп аталады ( шыңдар) және сегменттер ( қабырғалар), оның екі ұшы да берілген нүктелер жиынына жатады (2.1-суретті қараңыз).

(СУРЕТ 2.1)

Келесіде графтың төбелерін латын әріптерімен белгілейміз А , Б ,C ,D. Кейде график тұтастай бір бас әріппен белгіленеді.

Анықтама 2.02.Графиктің ешбір шетіне жатпайтын төбелері деп аталады оқшауланған .

Анықтама 2.03.Тек оқшауланған төбелерден тұратын график деп аталады нөл - санау .

Белгіленуі: О " – шеттері жоқ төбелері бар график (2.2-сурет).

(2.2-сурет)

Анықтама 2.04.Әрбір төбелер жұбы жиекпен қосылған график деп аталады толық .

Белгіленуі: У " – тұратын график nосы шыңдардың барлық мүмкін жұптарын қосатын шыңдар мен жиектер. Мұндай графикті келесідей көрсетуге болады n– барлық диагональдары сызылған үшбұрыш (2.3-сурет).

(2.3-СУРЕТ)

Анықтама 2.05. Дәреже шыңдаршыңы жататын жиектер саны.

Белгіленуі: б (А) – шыңы дәрежесі А . Мысалы, 2.1-суретте: б (А)=2, б (Б)=2, б (C)=2, б (D)=1, б (Е)=1.

Анықтама 2.06.Санақ, барлығының дәрежесі ктөбелері бірдей деп аталады біртекті санау градус к .

2.4 және 2.5-суреттерде екінші және үшінші дәрежелі біртекті графиктер көрсетілген.

(2.4 және 2.5-суреттер)

Анықтама 2.07. Қосымша берілген графиктолық графикті алу үшін бастапқы графикке қосылуы керек барлық шеттері мен олардың ұштарынан тұратын график.

2.6-суретте бастапқы график көрсетілген Г , төрт төбеден және үш кесіндіден тұратын және 2.7-суретте – осы графиктің толықтаушысы – график. Г " .

(2.6 және 2.7-суреттер)

2.5-суретте қабырғалардың бар екенін көреміз А.С.Және BDграфтың төбесі болып табылмайтын нүктеде қиылысады. Бірақ берілген графикті жазықтықта оның жиектері тек шыңдарда қиылысатындай етіп көрсету қажет болатын жағдайлар бар (бұл мәселе 5-тармақта толығырақ қарастырылады).

Анықтама 2.08.Жазықтықта оның шеттері тек төбелерінде қиылысатындай етіп кескіндеуге болатын график деп аталады. жазық .

Мысалы, 2.8-суретте 2.5-суреттегі графикке изоморфты (тең) болатын жазық график көрсетілген. Дегенмен, қарама-қарсы дұрыс болғанымен, әрбір графиктің жазық емес екенін ескеріңіз, яғни кез келген жазық графикті әдеттегі формада көрсетуге болады.

(2.8-СУРЕТ)

Анықтама 2.09.Графиктің төбелері мен шеттері болмайтын жазық графтың көпбұрышы деп аталады жиегі .

2016 оқу жылы Жыл

1. Кіріспе

2. Графтар теориясының пайда болу тарихы

3. Графтар теориясының негізгі түсініктері

4. Графтар теориясының негізгі теоремалары

5. Графиктерді компьютерде бейнелеу әдістері

6. Графтар теориясының есептерін қарастыру

7. Қорытынды

8. Әдебиеттер

Кіріспе

Соңғы уақытта дискретті математикамен дәстүрлі түрде байланысты салалардағы зерттеулер барған сайын көрнекті бола бастады. Математиканың математикалық талдау сияқты классикалық салаларымен қатар, дифференциалдық теңдеулер, В оқу бағдарламасы«Қолданбалы математика» мамандығында және басқа да көптеген мамандықтарда математикалық логика, алгебра, комбинаторика және графиктер теориясы бойынша бөлімдер пайда болды. Мұның себептерін осы математикалық аппараттың негізінде шешілетін есептердің ауқымын жай ғана анықтау арқылы түсіну қиын емес.

Графтар теориясының пайда болу тарихы.

1. Кенигсберг көпірлері туралы мәселе.Суретте. 1 Пергола өзенінің екі жағалауын, ондағы екі аралды және жеті байланыстырушы көпірді қамтитын Кенигсберг (қазіргі Калининград) қаласының орталық бөлігінің схемалық жоспарын көрсетеді. Тапсырма – жердің төрт бөлігін түгел айналып өтіп, әр көпірден бір рет өтіп, бастапқы нүктеге оралу. Бұл мәселені Эйлер 1736 жылы шешті (шешімі жоқ екені көрсетілді).

күріш. 1

2. Үш үй мен үш құдық мәселесі.Үш үй мен үш құдық бар, әйтеуір ұшақта орналасқан. Әр үйден әр құдыққа жолдар қиылыспайтындай етіп сызыңыз (2-сурет). Бұл мәселені 1930 жылы Куратовский шешті (шешімі жоқ екенін көрсетті).

күріш. 2

3. Төрт түсті мәселе.Жазықтықты қабаттаспайтын аймақтарға бөлу карта деп аталады. Картадағы аймақтар, егер олардың ортақ шекарасы болса, іргелес деп аталады. Тапсырма – картаны екі көршілес аумақ бірдей түспен боямайтындай етіп бояу (3-сурет). Өткен ғасырдың соңынан бастап бұл үшін төрт түстің жеткілікті екендігі туралы гипотеза белгілі болды. 1976 жылы Appel және Heiken компьютерлік іздеуге негізделген төрт түсті мәселенің шешімін жариялады. Бұл мәселені «бағдарламалық жолмен» шешу қызу пікірталас тудырған прецедент болды, ол әлі аяқталмаған. Жарияланған шешімнің мәні төрт түсті теоремаға ықтимал қарсы мысалдардың үлкен, бірақ шектеулі (шамамен 2000) түрлерін сынап көру және бірде-бір жағдайдың қарсы мысал емес екенін көрсету. Бұл іздеуді бағдарлама шамамен мың сағаттық суперкомпьютер жұмысында аяқтады. Алынған шешімді «қолмен» тексеру мүмкін емес - санау көлемі адам мүмкіндіктерінен әлдеқайда асып түседі. Көптеген математиктер сұрақ қояды: мұндай «бағдарламалық дәлелді» жарамды дәлел деп санауға бола ма? Өйткені, бағдарламада қателер болуы мүмкін... Бағдарламалардың дұрыстығын формальды түрде дәлелдеу әдістері талқыланатындай күрделі бағдарламаларға қолданылмайды. Тестілеу қателердің жоқтығына кепілдік бере алмайды және бұл жағдайда әдетте мүмкін емес. Осылайша, біз авторлардың бағдарламалау дағдыларына ғана сене аламыз және олардың бәрін дұрыс жасады деп сене аламыз.

Күріш. 3

Графтар теориясының негізгі түсініктері

1) G(V,E) графигіекі жиынның жиыны – бос емес V жиыны (төбелер жиыны) және V жиынының екі элементті ішкі жиындарының E жиыны (E – жиектер жиыны).

2) бағдарланған(x,y) түрінің реттелген жұп төбелерінің жиыны болатын график, мұнда x басы деп аталады, ал у доғаның соңы. Доға (x, y) жиі ретінде жазылады. Сондай-ақ олар доғаның х шыңынан у шыңына және у шыңына апаратынын айтады іргелесх шыңымен.

3) Е жиынының элементі жұп бола алатын болса бірдей(ерекше емес) V элементтері болса, онда Е жиынының мұндай элементі деп аталады цикл, және график деп аталады циклдері бар график(немесе псевдограф).

4) Егер E жиыны болмаса, бірақ орнатуқұрамында бірнеше бірдей элементтер болса, онда бұл элементтер деп аталады бірнеше жиектер, және график деп аталады мультиграф.

5) Е жиынының элементтері міндетті түрде екі элемент емес, V жиынының кез келген ішкі жиындары болса, онда Е жиынының мұндай элементтері деп аталады. гипердоғалар, және график деп аталады гиперграф.

6) Егер функция көрсетілген болса F: V → Mжәне/немесе F: E → M, содан кейін жиынтық Мжиынтық деп аталады ескертпелер, және график деп аталады белгіленген(немесе жүктелді). Таңбалар жиыны әдетте әріптер немесе бүтін сандар болып табылады. Егер функция Финъекциялық болып табылады, яғни әртүрлі төбелердің (жиектердің) әртүрлі белгілері бар, содан кейін график деп аталады. нөмірленген.

7) Субграф G′(V′,E′) графигі деп аталады, мұндағы және/немесе .

а) V′ = V болса, онда G′ деп аталады негізгі G тармақшасы.

б) Егер болса, онда G′ графигі шақырылады меншікГ графының тармақшасы.

в) G′(V′,E′) графигі G(V,E) графының қалыпты графигі деп аталады, егер G′ ішінде G-ның барлық мүмкін болатын шеттері болса.

8) Дәреже (валенттілік)шыңдар - осы төбеге түсетін жиектер саны (оған іргелес шыңдар саны).

9) Маршрутграфикте кез келген екі көршілес элемент түсетін төбелер мен шеттердің ауыспалы тізбегі.

а) Егер , онда маршрут жабық, әйтпесе ашық.

б) Егер барлық жиектер әртүрлі болса, онда маршрут шақырылады шынжыр.

в) Егер барлық шыңдар (демек, шеттер) әртүрлі болса, онда маршрут шақырылады қарапайым тізбек.

г) Тұйық тізбек деп аталады цикл.

д) Тұйық қарапайым тізбек деп аталады қарапайым цикл.

f) Циклдері жоқ график деп аталады ациклді.

ж) Диграфтар үшін тізбек деп аталады бойынша, және цикл болады контур.

күріш. 4. Маршруттар, тізбектер, циклдар

Мысал

Диаграммасы 4-суретте көрсетілген графикте:

1. v 1, v 3, v 1, v 4 – маршрут, бірақ тізбек емес;

2. v 1, v 3, v 5, v 2, v 3, v 4 – тізбек, бірақ қарапайым тізбек емес;

3. v 1, v 4, v 3, v 2, v 5 – қарапайым тізбек;

4. v 1, v 3, v 5, v 2, v 3, v 4, v 1 – цикл, бірақ қарапайым цикл емес;

5. v 1, v 3, v 4, v 1 – қарапайым цикл.

10) Егер графикте графтың барлық шеттерін бір рет қамтитын цикл (міндетті түрде қарапайым емес) болса, онда мұндай цикл деп аталады. Эйлерцикл.

11) Егер графикте графтың барлық төбелері (бір уақытта) тұратын қарапайым цикл болса, онда мұндай цикл деп аталады Гамильтондықцикл.

12) ағашциклсыз байланысқан график деп аталады.

13) қаңқаГрафиктің барлық төбелері бар ағаш деп аталады.

14) СәйкестікЕкеуі қатарласпайтын жиектер жиынтығы.

15) Сәйкестік шақырылады максимум, егер оның жоғарғы жиыны тәуелсіз болмаса.

16) Графиктің екі төбесі қосылған, егер оларды байланыстыратын қарапайым тізбек болса.

17) Барлық төбелері қосылған график деп аталады когерентті.

18) Тек оқшауланған төбелерден тұратын график деп аталады әбден үйлесімсіз.

19) Маршрут ұзындығыондағы жиектер саны деп аталады (қайталаумен).

20) Қашықтық u және v төбелерінің арасындағы ең қысқа тізбектің ұзындығы деп, ал ең қысқа тізбектің өзі деп аталады геодезиялық.

21) Диаметрі G графының ең ұзын геодезиялық ұзындығы деп аталады.

22) Эксцентристік G(V,E) қосылған графтағы v шыңы - v төбесінен G графының басқа төбелеріне дейінгі ең үлкен қашықтық.

23) Радиус G графының төбелерінің эксцентриситеттерінің ең кішісі деп аталады.

24) v Vertex деп аталады орталық, егер оның эксцентриситеті графиктің радиусымен сәйкес келсе.

25) Орталық төбелер жиыны деп аталады орталықграфик.

күріш. 5 Графиктердің төбелері мен центрлерінің эксцентриситеттері (ерекшеленген).

Қатысты ақпарат.

Википедия материалы – еркін энциклопедия

Графикалық теория- графиктердің қасиеттерін зерттейтін дискретті математиканың бөлімі. Жалпы мағынада график жиын ретінде берілген шыңдар(түйіндер) қосылған қабырғалар. Қатаң анықтамада мұндай жиындар жұбы график деп аталады. $G\; =\; (V,\; E)$, Қайда $В$кез келген есептелетін жиынның ішкі жиыны болып табылады және $Е$- ішкі жиын $V\backslash рет\; V$.

Графикалық теория қолдануды, мысалы, географиялық ақпараттық жүйелерде (ГАЖ) табады. Қолданыстағы немесе жаңадан жобаланған үйлер, құрылыстар, блоктар және т.б. шыңдар деп, ал оларды байланыстыратын жолдар, инженерлік желілер, электр желілері және т.б. жиектерге жатады. Мұндай графикте орындалатын әртүрлі есептеулерді пайдалану, мысалы, ең қысқа айналма жолды немесе ең жақын азық-түлік дүкенін табуға немесе оңтайлы маршрутты жоспарлауға мүмкіндік береді.

Графикалық теория қамтиды көп санышешілмеген мәселелер және әлі дәлелденбеген гипотезалар.

Графтар теориясының тарихы

Леонард Эйлер графтар теориясының негізін салушы болып саналады. 1736 жылы ол өзінің бір хатында Кенигсбергтің жеті көпірі мәселесінің шешімін тұжырымдап, ұсынды, ол кейінірек графтар теориясының классикалық мәселелерінің біріне айналды.

Графикалық теория терминологиясы

Графиктерді жазықтықта бейнелеу

Графиктерді суреттерде бейнелеу кезінде ол жиі қолданылады келесі жүйебелгілеулер: графиктің төбелері нүктелер түрінде немесе төбенің мағынасын көрсеткенде тіктөртбұрыштар, сопақшалар және т.б. бейнеленген, мұнда төбенің мәні фигураның ішінде ашылады (алгоритм блок-схемаларының графиктері). Егер шыңдар арасында жиек болса, онда сәйкес нүктелер (фигуралар) сызық немесе доға арқылы қосылады. Бағытталған график жағдайында доғалар көрсеткілермен ауыстырылады немесе жиектің бағыты анық көрсетіледі. Кейде түсіндірме жазулар жиектің жанына қойылып, жиектің мағынасын ашады, мысалы, ақырлы күй машиналарының ауысу графиктерінде. Жазық және жазық емес графиктер болады. Жазық график деп суретте (жазықтықта) қиылысатын жиектері жоқ (ең қарапайымдары үшбұрыш немесе қосылған төбелер жұбы) бейнелеуге болатын графикті айтады, әйтпесе график жазық емес болады. Графикте циклдар болмаған жағдайда (кем дегенде бір жолды қамтиды бір ретбастапқы шыңға оралумен жиектер мен шыңдарды кесіп өту), әдетте «ағаш» деп аталады. Графтар теориясындағы ағаштардың маңызды түрлері екілік ағаштар болып табылады, олардың әрбір төбесінде бір кіріс және дәл екі шығыс шеті бар немесе соңғы болып табылады - шығыс жиектері жоқ және кіріс жиегі жоқ бір түбір төбесінен тұрады.

Графиктің кескінін графтың өзімен (абстрактілі құрылым) шатастырмау керек, өйткені бір графикпен бірнеше графикалық көріністі байланыстыруға болады. Кескін тек шыңдардың қай жұптары жиектермен қосылғанын және қайсысы қосылмағанын көрсетуге арналған. Екі сурет бір графиктің моделі бола ма, жоқ па (басқаша айтқанда, кескіндерге сәйкес графиктер изоморфты ма) деген сұраққа жауап беру практикада жиі қиын. Тапсырмаға байланысты кейбір кескіндер басқаларға қарағанда айқындылықты қамтамасыз етуі мүмкін.

Графтар теориясының кейбір мәселелері

• Кенигсберг мәселесінің жеті көпірі графтар теориясының алғашқы нәтижелерінің бірі болып табылады, оны Эйлер басып шығарған.
• Төрт түсті есеп 1852 жылы тұжырымдалған, бірақ классикалық емес дәлелдеу тек 1976 жылы алынған (шардағы (жазықтықтағы) карта үшін 4 түс жеткілікті).
• Саяхатшы сатушы мәселесі - ең танымал NP-толық есептердің бірі.
• Клик мәселесі NP-толық басқа мәселе болып табылады.
• Ең аз созылатын ағашты табу.
• Графикалық изоморфизм – бір графтың төбелерін қайта нөмірлеу арқылы басқасын алуға болады ма?
• Графиктің жазықтықтылығы – графикті жиектердің қиылысуынсыз (немесе баспа тақшаларының немесе микросұлбалардың элементтерінің өзара байланысын қадағалағанда қолданылатын қабаттардың ең аз санымен) жазықтықта бейнелеу мүмкін бе?

Графтар теориясын қолдану

да қараңыз

«График теориясы» мақаласы бойынша пікір жазыңыз.

Ескертпелер

Әдебиет

• Distel R.Графикалық теория Транс. ағылшын тілінен – Новосибирск: Математика институтының баспасы, 2002. – 336 б. ISBN 5-86134-101-X.
• Дизтель Р.. - NY: Springer-Verlag, 2005. - 422-б.
• Басакер Р., Сааты Т.
• Белов В.В., Воробьев Е.М., Шаталов В.Е.Графикалық теория. - М.: Жоғары. мектеп, 1976. – 392 б.
• Берге К.
• Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.Графтар теориясы бойынша дәрістер. М.: Наука, 1990. 384 б. (2-бас., қайта қаралған М.: URSS, 2009. 392 б.)
• Зыков А.А.. - М.: «Университет кітабы», 2004. - 664-б. - ISBN 5-9502-0057-8.(М.: Наука, 1987. 383c.)
• Топология мен графиктер теориясының химиялық қолданулары. Ред. Р.Кинг. Пер. ағылшын тілінен М.: Мир, 1987 ж.
• Кирсанов М.Н. Maple тіліндегі графиктер. М.: Физматлит, 2007. 168 б. vuz.exponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Христофид Н.
• Кормен Т.Х. және т.б. VI бөлім. Графиктермен жұмыс істеу алгоритмдері // Алгоритмдер: құрастыру және талдау = Алгоритмдерге кіріспе. - 2-ші басылым. - М.: Уильямс, 2006. - Б. 1296. - ISBN 0-07-013151-1.
• Кен О.. - 2-ші басылым. – М.: Ғылым, 1980. – 336 б.
• Салий В.Н. Богомолов А.М.. - М.: Физика-математика әдебиеті, 1997. - ISBN 5-02-015033-9.
• Свами М., Туласираман К.
• Тутт В.
• Уилсон Р.
• Харари Ф.. - М.: Мир, 1973 ж.(3-бас., М.: КомКнига, 2006. – 296 б.)
• Харари Ф., Палмер Э.. - Әлем, 1977 ж.
• Сергей Мельников// Ғылым және өмір. - 1996. - Шығарылым. 3. - 144-145 беттер.Мақала Густав Симмонс ойлап тапқан Sim графикалық ойыны туралы.

Сілтемелер

• : пайдаланушыға графиктердегі ақпаратты визуализациялау және іздеу үшін құралдар мен әдістердің кең спектрін ұсынатын бағдарлама

Классикалық талдау Функция теориясы Дифференциалды және интегралдық теңдеулер

Графикалық теорияны сипаттайтын үзінді

Бірақ бұл сөздерді аяқтамай тұрып, князь Андрей ұят пен ашудың көз жасын сезініп, аттан секіріп, туға қарай жүгіре бастады.
- Балалар, алға! – деп балаша айқайлады.
«Міне ол!» — деп ойлады князь Андрей тудың бағанасын ұстап алып, оқтардың ысқырығын рахаттана естіп, оны арнайы көздегені анық. Бірнеше солдат құлады.
- Ура! – деп айқайлады князь Андрей қолындағы ауыр туды әрең ұстап, бүкіл батальон оның соңынан жүгіретініне күмәнсіз сеніммен алға қарай жүгірді.
Шынында да, ол бірнеше қадам ғана жалғыз жүгірді. Бір солдат, сосын екіншісі жолға шықты, бүкіл батальон «Ура!» деп айғайлады. алға жүгіріп, оны қуып жетті. Батальонның сержанты жүгіріп келіп, князь Андрейдің қолындағы салмақтан дірілдеп тұрған туды алды, бірақ бірден өлтірілді. Князь Андрей тағы да туды ұстап алып, оны сырықтан сүйреп, батальонмен бірге қашып кетті. Оның алдында ол біздің артиллеристтерді көрді, олардың кейбіреулері соғысып, басқалары зеңбіректерін тастап, оған қарай жүгірді; артиллериялық аттарды ұстап алып, мылтықтарды бұрған француз жаяу әскерлерін де көрді. Князь Андрей мен оның батальоны мылтықтардан 20 қадам жерде болды. Үстінен тынымсыз ысқырған оқтарды естіп, сарбаздар үнемі ыңылдап, оңды-солды құлады. Бірақ ол оларға қарамады; ол тек алдында не болып жатқанына – батареяға қарады. Ол бір жағында шаншыған қызыл шашты артиллеристтің бір жағын қағып, бір жағында туды тартып жатқанын, ал екінші жағында француз солдаты туды өзіне қарай тартып бара жатқанын анық көрді. Князь Андрей бұл екі адамның не істеп жатқанын түсінбеген сияқты жүздеріндегі абдырап, сонымен бірге ашуланған өрнекті анық көрді.
«Олар не істеп жатыр? - деп ойлады князь Андрей оларға қарап: - қызыл шашты артиллерист қаруы жоқ кезде неге жүгірмейді? Неліктен француз оған пышақ салмайды? Оған жеткенше француз мылтықты есіне түсіріп, оны пышақтап өлтіреді».
Шынында да, мылтық асынған тағы бір француз жауынгерлерге қарай жүгірді, ал өзін не күтіп тұрғанын әлі түсінбей, жеңіспен туды жұлып алған қызыл шашты артиллеристтің тағдыры шешілетін болды. Бірақ князь Андрей оның қалай аяқталғанын көрмеді. Оған жақын маңдағы жауынгерлердің бірі күшті таяқты сермеп жібергендей басынан ұрғандай көрінді. Бұл аздап ауырды, ең бастысы, бұл жағымсыз болды, өйткені бұл ауырсыну оның көңілін көтеріп, оның қарап тұрғанын көруге кедергі келтірді.
«Бұл не? мен құлап жатырмын ба? Аяғым босап жатыр», – деп ойлады да, шалқасынан құлады. Француздар мен артиллеристтердің шайқасы қалай аяқталғанын көргісі келіп, қызыл шашты артиллерист өлді ме, жоқ па, мылтық алынды ма, аман қалды ма, соны білгісі келіп, көзін ашты. Бірақ ол ештеңе көрмеді. Оның үстінде аспаннан басқа ештеңе жоқ еді - биік аспан, анық емес, бірақ әлі де өлшеусіз биік, сұр бұлттар оны бойымен ақырын жылжып келеді. «Қандай тыныш, байсалды және салтанатты, менің жүгіргенім сияқты емес, - деп ойлады князь Андрей, - біздің жүгіргеніміз, айқайлағанымыз және соғысқанымыз сияқты емес; Бұл француз мен артиллеристтің ашулы және үрейлі жүздерімен бір-бірінің туын тартып алғанына мүлдем ұқсамайды - бұлттардың осы шексіз биік аспан арқылы жорғалағаны мүлдем ұқсамайды. Мен бұл биік аспанды бұрын қалай көрмедім? Ақырында оны танығаныма қандай қуаныштымын. Иә! бәрі бос, бәрі алдау, мынау шексіз аспаннан басқа. Одан басқа ештеңе, ештеңе жоқ. Бірақ ол жоқ болса да, тыныштық, тыныштықтан басқа ештеңе жоқ. Және Құдайға шүкір!…”

Багратионның оң қапталында сағат 9-да жұмыс әлі басталған жоқ. Долгоруковтың бизнесті бастау талабымен келіспеу және жауапкершілікті өзінен аластату үшін князь Багратион Долгоруковты бас қолбасшыдан бұл туралы сұрауға жіберуді ұсынды. Багратион бір қапталды екіншісінен 10 верстке жуық арақашықтыққа байланысты, егер жіберілген адам өлтірілмесе (бұл өте ықтимал), тіпті бас қолбасшыны тапса да, бұл өте қиын екенін білді. Жіберілген адам ерте кешке қайтып үлгермейді.
Багратион үлкен, мәнерсіз, ұйқысыз көздерімен жан-жағына қарады, ал Ростовтың толқу мен үміттен еріксіз қатып қалған бала жүзі бірінші болып көзіне түсті. Ол жіберді.
– Мәртебелі Жоғарғы Бас қолбасшының алдында кездессем ше? – деді Ростов қолын визорға ұстап.
— Сіз оны ұлы мәртебеліге тапсыра аласыз, — деді Долгоруков Багратионның сөзін асығыс бөліп.
Тізбектен босатылған Ростов таңертеңге дейін бірнеше сағат ұйықтай алды және қимылдардың икемділігімен, өзінің бақытына сенімділігімен және бәрі оңай, көңілді және мүмкін болып көрінетін көңіл-күймен өзін көңілді, батыл, шешуші сезінді.
Сол күні таңертең оның барлық тілектері орындалды; жалпы шайқас болды, оған қатысты; Оның үстіне ол ең батыл генералдың қол астындағы тәртіпті болды; Оның үстіне, ол Кутузовқа, тіпті егеменнің өзіне де тапсырыспен бара жатқан. Таңның атысы ашық, астындағы ат жақсы. Оның жаны жайдарлы, бақытты болды. Бұйрығын алып, атын жөнелтіп, желі бойымен шабады. Алдымен ол әлі әрекетке кіріспеген және қозғалыссыз тұрған Багратион әскерлерінің сызығымен жүрді; содан кейін ол Уваровтың атты әскері алып жатқан кеңістікке кірді және бұл жерде қозғалыстар мен іске дайындық белгілерін байқады; Уваровтың атты әскерінің алдынан өтіп, оның алдында зеңбірек пен мылтық даусын анық естіді. Атыс күшейе түсті.
Таңертеңгілік таза ауада бұрынғыдай ретсіз аралықпен екі, үш, сосын бір-екі мылтық атыстары естілмеді, ал тау баурайында, Пратценнің алдында мылтық дауыстары естіліп, үзілді. зеңбіректердің жиі атыстары соншалық, кейде бірнеше зеңбіректер бір-бірінен ажырамай, бір ортақ гүрілге біріктірілді.
Мылтық түтіні бір-бірін қуып жетіп, еңістерді бойлай жүгіріп бара жатқаны, мылтықтардың түтіні бұралып, бұлдырап, бір-біріне қосылып кеткені көрінді. Түтіннің арасынан штыктардың жарқырауынан жаяу әскерлер мен жасыл жәшіктері бар тар артиллерияның қозғалатын массалары көрінді.
Ростов не болып жатқанын тексеру үшін төбеде бір минутқа атын тоқтатты; бірақ ол қанша зейінін аударса да, не болып жатқанын түсіне де, ажырата да алмады: әлдекімдер сол жерде түтінге оранып, әлдебір жасақ полотносы алдынан да, артында да қозғалып жатты; бірақ неге? ДДСҰ? Қайда? түсіну мүмкін емес еді. Бұл көрініс пен бұл дыбыстар оның бойында ешбір күңгірт, ұялшақ сезім тудырып қана қойған жоқ, керісінше, күш-қуат пен жігер берді.
«Ал, көбірек, көбірек бер!» – Ол бұл дыбыстарға ойша бұрылды да, әрекетке кіріскен әскерлер аймағына одан әрі еніп, сызық бойымен қайтадан жүгіре бастады.
«Ол жерде қалай болатынын білмеймін, бірақ бәрі жақсы болады!» — деп ойлады Ростов.
Біраз австриялық әскерлерден өтіп, Ростов саптың келесі бөлігі (бұл күзет болды) әрекетке кіріскенін байқады.
«Бәрі жақсы! Мен жақынырақ қараймын», - деп ойлады ол.
Ол майдан шебінің бойымен дерлік жүрді. Бірнеше салт атты оған қарай жүгірді. Бұлар шабуылдан тәртіпсіз саппен қайтып келе жатқан біздің өмірлік зымырандар еді. Ростов олардың жанынан өтіп бара жатып, еріксіз олардың біреуін қанға боялғанын байқады және жүгіре жөнелді.
«Маған бұл маңызды емес!» ол ойлады. Ол бірнеше жүз қадам аттап үлгермес бұрын, оның сол жағында, бүкіл даланың бойымен, қара аттар мінген, жылтыр ақ киім киген атты әскерлердің үлкен тобы оған қарай жүгірді. Ростов бұл атты әскерлердің жолынан таймау үшін атын қатты шаба жөнелді, егер олар бірдей жүріспен жүрсе, ол олардан қашып кетер еді, бірақ олар жылдамдықты арттыра берді, сондықтан кейбір аттар шаба бастады. Ростовтықтар олардың тепкілеп, қару-жарақтарының тарсылдағанын барған сайын анық естіп, аттары, фигуралары, тіпті беттері де көріне бастады. Бұлар өздеріне қарай жылжып келе жатқан француз атты әскеріне шабуылға бара жатқан біздің атты гвардиялар еді.
Атты қарауылдар шаба жөнелді, бірақ әлі де аттарын ұстап тұрды. Ростов олардың жүздерін көріп, «марш, марш!» деген бұйрықты естіді. - деп қанды атын бар жылдамдықпен босатқан офицер айтты. Француздардың шабуылына ұшырап қалудан немесе азғырудан қорыққан Ростов майданда атының шама-шарқынша шаба жөнелді, бірақ әлі де олардың жанынан өте алмады.
Алдынан еріксіз соқтығысатын Ростовты көргенде, ең соңғы атты гвардия, дәу, қалталы адам ашулы қабағын түйіп алды. Бұл атты гвардия Ростовты да, оның бәдәуиін де (осы алып адамдар мен аттармен салыстырғанда Ростовтың өзі соншалықты кішкентай және әлсіз болып көрінетін), атты сақшы аттың көзіне қамшысын сермеуді ойламағанда, әрине, құлатар еді. Қара, ауыр, бес дюймдік жылқы құлағын шалқайтып, қашқақтады; бірақ қалталы атты күзетші оның бүйірлеріне үлкен шпорларды қағып жіберді, ал құйрығын бұлғап, мойнын созған жылқы одан да жылдам жүгірді. Атты гвардия Ростовтан өткен бойда олардың: «Ура!» деп айғайлағанын естіді. ал артына қараса, олардың алдыңғы қатарлары бөтен адамдармен, бәлкім француздармен, қызыл погон киген атты әскерлермен араласып жатқанын көрді. Одан әрі ештеңені көру мүмкін болмады, өйткені осыдан кейін бірден бір жерден зеңбіректер атқылап, бәрі түтінге оранды.
Осы кезде оның жанынан өтіп бара жатқан атты гвардия түтінге сіңіп кеткенде, Ростов олардың соңынан жүгірер ме, әлде баратын жеріне барар ма екен деп ойлады. Бұл француздарды таң қалдырған атты гвардияшылардың керемет шабуылы болды. Ростовты кейінірек естігенде, осынша үлкен әдемі адамдардан, мыңдаған атқа мінген тамаша, бай жігіттерден, оның жанынан өтіп бара жатқан офицерлер мен курсанттардан шабуылдан кейін он сегіз адам қалды.