Գրաֆների տեսության հիմունքները, ծագման և զարգացման պատմությունը: Ի՞նչ է գրաֆիկը Գրաֆ. սահմանում - History.NES Գրաֆների տեսության պատմություն

գագաթները(հանգույցներ) միացված կողիկներ. Խիստ սահմանմամբ գրաֆիկը նման զույգ բազմություններ է G = (V, E) (\displaystyle G=(V,E)), Որտեղ V (\displaystyle V)ցանկացած հաշվելի բազմության ենթաբազմություն է, և E (\displaystyle E)- ենթաբազմություն V × V (\ցուցադրման ոճ V\ անգամ V).

Գրաֆիկների տեսությունը կիրառություն է գտնում, օրինակ, աշխարհագրական տեղեկատվական համակարգերում (GIS): Գագաթներ են համարվում գոյություն ունեցող կամ նոր նախագծված տները, շինությունները, բլոկները և այլն, իսկ եզրեր են համարվում դրանք միացնող ճանապարհները, կոմունալ ցանցերը, էլեկտրահաղորդման գծերը և այլն։ Նման գրաֆիկի վրա կատարված տարբեր հաշվարկների օգտագործումը թույլ է տալիս, օրինակ, գտնել ամենակարճ շրջանցման երթուղին կամ մոտակա մթերային խանութը կամ պլանավորել օպտիմալ երթուղին։

Գրաֆիկների տեսությունը պարունակում է մեծ թվով չլուծված խնդիրներ և դեռևս չապացուցված վարկածներ։

Գրաֆիկների տեսության պատմություն

Լեոնարդ Էյլերը համարվում է գրաֆիկների տեսության հիմնադիրը։ 1736 թվականին նա իր նամակներից մեկում ձևակերպել և առաջարկել է Քյոնիգսբերգի յոթ կամուրջների խնդրի լուծումը, որը հետագայում դարձել է գրաֆիկների տեսության դասական խնդիրներից մեկը։ «Գրաֆիկ» տերմինը առաջին անգամ ստեղծվել է Սիլվեստր Ջեյմս Ջոզեֆի կողմից 1878 թվականին Nature-ում իր հոդվածում [ ] .

Գրաֆիկների տեսության տերմինաբանություն

Գրաֆների տեսության կիրառում

տես նաեւ

Նշումներ

գրականություն

• Դիստել Ռ.Գրաֆի տեսություն Տրանս. անգլերենից - Նովոսիբիրսկ: Մաթեմատիկայի ինստիտուտի հրատարակչություն, 2002 թ. - 336 էջ. ISBN 5-86134-101-X.
• Դիզել Ռ.Գրաֆի տեսություն, Էլեկտրոնային հրատարակություն: - NY: Springer-Verlag, 2005. - P. 422:
• Բասաքեր Ռ., Սաատի Թ.Վերջավոր գրաֆիկներ և ցանցեր: M.: Nauka, 1974. 368c.
• Բելով Վ.Վ., Վորոբիև Է.Մ., Շատալով Վ.Է.Գրաֆիկի տեսություն. - Մ.: Ավելի բարձր: դպրոց, 1976. - P. 392:
• Պերճ Կ.Գրաֆիկների տեսությունը և դրա կիրառությունները. M.: IL, 1962. 320c.
• Էմելիչև Վ.Ա., Մելնիկով Օ.Ի., Սարվանով Վ.Ի., Տիշկևիչ Ռ.Ի.Դասախոսություններ գրաֆիկների տեսության վերաբերյալ. M.: Nauka, 1990. 384 p. (Խմբ. 2, վերանայված M.: URSS, 2009. 392 p.)

Լեոնարդ Էյլերը համարվում է գրաֆիկների տեսության հիմնադիրը։ 1736 թվականին նա իր նամակներից մեկում ձևակերպել և առաջարկել է Քյոնիգսբերգի յոթ կամուրջների խնդրի լուծումը, որը հետագայում դարձել է գրաֆիկների տեսության դասական խնդիրներից մեկը։

Գրաֆների տեսության առաջին խնդիրները կապված էին մաթեմատիկական հանգստի խնդիրների և գլուխկոտրուկների լուծման հետ: Ահա մի հատված Էյլերի նամակից՝ թվագրված 1736 թվականի մարտի 13-ին. «Ինձ խնդիր տրվեց մի կղզու մասին, որը գտնվում է Քյոնիգսբերգ քաղաքում և շրջապատված գետով, որի վրայով 7 կամուրջներ կան: Հարցն այն է, թե ինչ-որ մեկը կարո՞ղ է անընդհատ շրջել դրանց շուրջը՝ յուրաքանչյուր կամրջի վրայով միայն մեկ անգամ անցնելով։ Եվ հետո ինձ տեղեկացրին, որ դեռ ոչ ոք չի կարողացել դա անել, բայց ոչ ոք չի ապացուցել, որ դա անհնար է։ Այս հարցը, թեև չնչին, ինձ թվում էր, այնուամենայնիվ, ուշադրության արժանի, քանի որ ոչ երկրաչափությունը, ոչ հանրահաշիվը և ոչ էլ կոմբինատոր արվեստը բավարար չեն այն լուծելու համար։ Երկար մտածելուց հետո ես գտա մի հեշտ կանոն, որը հիմնված է միանգամայն համոզիչ ապացույցի վրա, որի օգնությամբ հնարավոր է բոլոր նմանատիպ խնդիրների դեպքում անմիջապես որոշել, թե արդյոք կարելի է նման շրջանցում կատարել ցանկացած թվով և ցանկացած թվով: կամուրջներ, որոնք գտնվում են ինչ-որ կերպ, թե ոչ»։ Քյոնիգսբերգի կամուրջները սխեմատիկորեն կարելի է պատկերել հետևյալ կերպ.

Էյլերի կանոն.

1. Գրաֆիկի մեջ, որը չունի կենտ աստիճանի գագաթներ, կա բոլոր եզրերի անցում (և յուրաքանչյուր եզրը հատվում է ուղիղ մեկ անգամ), սկսած գրաֆիկի ցանկացած գագաթից:

2. Գրաֆիկի մեջ, որն ունի երկու և միայն երկու կենտ աստիճաններով գագաթներ, կա անցում, որը սկսվում է մի գագաթից կենտ աստիճանով և ավարտվում մյուսով:

3. Գրաֆիկում, որն ունի կենտ աստիճաններով երկուից ավելի գագաթներ, այդպիսի անցում գոյություն չունի:

Գոյություն ունի մեկ այլ տեսակի խնդիր՝ կապված գրաֆիկների երկայնքով ճանապարհորդելու հետ: Խոսքը խնդիրների մասին է, որոնց դեպքում անհրաժեշտ է գտնել բոլոր գագաթներով անցնող ուղի, և ոչ ավելի, քան յուրաքանչյուրի միջով: Յուրաքանչյուր գագաթով մեկ և միայն մեկ անգամ անցնող ցիկլը կոչվում է Համիլտոնյան գիծ (նախորդ դարի հայտնի իռլանդացի մաթեմատիկոս Ուիլյամ Ռոուեն Համիլթոնի անունով, ով առաջինն էր ուսումնասիրել նման գծերը): Ցավոք, դեռևս չի գտնվել մի ընդհանուր չափանիշ, որի օգնությամբ կարելի է որոշել՝ արդյոք տվյալ գրաֆիկը Համիլտոնյան է, և եթե այո, ապա դրա վրա գտնել բոլոր Համիլտոնյան տողերը։

Ձևակերպվել է 19-րդ դարի կեսերին։ Չորս գույնի խնդիրը նույնպես զվարճալի խնդիր է թվում, սակայն այն լուծելու փորձերը հանգեցրել են որոշ գրաֆիկական ուսումնասիրությունների, որոնք ունեն տեսական և կիրառական նշանակություն: Չորս գույնի խնդիրը ձևակերպված է հետևյալ կերպ. «Կարո՞ղ է արդյոք ցանկացած հարթ քարտեզի տարածքը գունավորվել չորս գույնով, որպեսզի ցանկացած երկու հարակից տարածքներ գունավորվեն տարբեր գույներով»: Պատասխանի դրական լինելու վարկածը ձեւակերպվել է 19-րդ դարի կեսերին։ 1890 թվականին ապացուցվեց ավելի թույլ հայտարարություն, այն է, որ ցանկացած հարթ քարտեզ կարելի է գունավորել հինգ գույներով: Ցանկացած հարթ քարտեզ կապելով իր երկակի հարթ գրաֆիկի հետ՝ մենք ստանում ենք խնդրի համարժեք ձևակերպում գրաֆիկների առումով. Ճի՞շտ է, որ ցանկացած հարթ գրաֆիկի քրոմատիկ թիվը չորսից փոքր է կամ հավասար: Խնդիրը լուծելու բազմաթիվ փորձեր ազդեցին գրաֆիկների տեսության մի շարք ոլորտների զարգացման վրա։ 1976 թվականին հայտարարվեց համակարգչի միջոցով խնդրի դրական լուծում։

Մեկ այլ հին տոպոլոգիական խնդիր, որը երկար ժամանակ առանձնապես դիմացկուն է լուծմանը և հետապնդում է գլուխկոտրուկների սիրահարների միտքը, հայտնի է որպես «էլեկտրաէներգիայի, գազի և ջրի մատակարարման խնդիր»: 1917 թվականին Հենրի Դուդենին տվել է այս ձևակերպումը. Նկարում ներկայացված երեք տներից յուրաքանչյուրում պետք է տեղադրվեն գազ, էլեկտրականություն և ջուր:

Գրաֆիկի տեսություն. 1

Գրաֆիկների տեսության առաջացման պատմությունը. 1

Էյլերի կանոն. 1

գրականություն

1. Բելովի գրաֆիկի տեսություն, Մոսկվա, «Գիտություն», 1968.

2. Նոր մանկավարժական և տեղեկատվական տեխնոլոգիաներ Է.Ս.Պոլատ , Մոսկվա, «Ակադեմիա» 1999 թ

3. Կուզնեցով Օ.Պ., Ադելսոն-Վելսկի Գ.Մ. Դիսկրետ մաթեմատիկա ինժեների համար: – Մ.: Էներգոատոմիզդատ, 1988.

4. Cook D., Baze G. Համակարգչային մաթեմատիկա. – Մ.: Գիտություն, 1990.

5. Նեֆեդով Վ.Ն., Օսիպովա Վ.Ա. Դիսկրետ մաթեմատիկայի դասընթաց. – M.: MAI հրատարակչություն, 1992.

6. Ore O. Գրաֆի տեսություն. – Մ.: Գիտություն, 1980.

7. Իսմագիլով Ռ.Ս., Կալինկին Ա.Վ. Դասընթացի գործնական պարապմունքների նյութեր՝ Դիսկրետ մաթեմատիկա

Գրաֆների տեսության հիմնադիրը համարվում է մաթեմատիկոս Լեոնհարդ Էյլերը (1707-1783): Այս տեսության պատմությանը կարելի է հետևել մեծ գիտնականի նամակագրության միջոցով։ Ահա լատիներեն տեքստի թարգմանությունը, որը վերցված է իտալացի մաթեմատիկոս և ինժեներ Մարինոնիին Էյլերի նամակից, որն ուղարկվել է Սանկտ Պետերբուրգից 1736 թվականի մարտի 13-ին [տես. էջ 41-42]:

«Մի անգամ ինձ հարց տվեցին մի կղզու մասին, որը գտնվում է Քյոնիգսբերգ քաղաքում և շրջապատված գետով, որի վրայով յոթ կամուրջներ են նետվում: Հարցն այն է, թե արդյոք որևէ մեկը կարող է անընդհատ շրջանցել դրանց շուրջը՝ յուրաքանչյուր կամրջով միայն մեկ անգամ անցնելով: Եվ հետո ես եղա: տեղեկացրեց, որ դեռևս ոչ ոք չի կարողացել դա անել, բայց ոչ ոք չի ապացուցել, որ դա անհնար է: Այս հարցը, թեև չնչին, ինձ թվում էր, այնուամենայնիվ, ուշադրության արժանի, քանի որ ոչ երկրաչափությունը, ոչ հանրահաշիվը և ոչ էլ կոմբինատոր արվեստը չեն. բավարար է այն լուծելու համար... Երկար մտածելուց հետո ես գտա մի հեշտ կանոն՝ հիմնված միանգամայն համոզիչ ապացույցի վրա, որի օգնությամբ կարելի է անմիջապես պարզել բոլոր այս կարգի խնդիրներում, թե արդյոք կարելի է նման շրջանցում կատարել ցանկացած միջոցով. կամուրջների թիվը, որոնք գտնվում են որևէ կերպ, թե ոչ, որպեսզի դրանք ներկայացված լինեն հետևյալ նկարում[նկ.1] , որտեղ A-ն նշանակում է կղզի, իսկ B, C և D՝ մայրցամաքի մասեր՝ միմյանցից բաժանված գետի ճյուղերով։ Յոթ կամուրջները պիտակավորված են a, b, c, d, e, f, g»:

(ՆԿԱՐ 1.1)

Այս կարգի խնդիրներ լուծելու իր հայտնաբերած մեթոդի վերաբերյալ Էյլերը գրել է [տես. էջ 102-104]:

«Այս լուծումն իր բնույթով, ըստ երևույթին, քիչ առնչություն ունի մաթեմատիկայի հետ, և ես չեմ հասկանում, թե ինչու պետք է այս լուծումը ակնկալել մաթեմատիկոսից, քան որևէ այլ անձից, քանի որ այս որոշումը հիմնավորվում է միայն պատճառաբանությամբ, և չկա: պետք է ներգրավել այս լուծումը գտնելու համար, մաթեմատիկային բնորոշ օրենքներ: Այսպիսով, ես չգիտեմ, թե ինչպես է ստացվում, որ մաթեմատիկայի հետ շատ քիչ առնչվող հարցերը ավելի հավանական է, որ լուծվեն մաթեմատիկոսների կողմից, քան մյուսների կողմից»:

Այսպիսով, հնարավո՞ր է շրջանցել Քյոնիգսբերգի կամուրջները՝ այս կամուրջներից յուրաքանչյուրի վրայով միայն մեկ անգամ անցնելով: Պատասխանը գտնելու համար շարունակենք Էյլերի նամակը Մարինոնիին.

0 «Հարցը կայանում է նրանում, որ պարզենք՝ հնարավո՞ր է արդյոք շրջանցել այս բոլոր յոթ կամուրջները՝ յուրաքանչյուրով մեկ անգամ անցնելով, թե ոչ։ Իմ կանոնը տանում է այս հարցի հետևյալ լուծմանը։ Նախ պետք է տեսնել, թե քանիսն են։ հատվածներն այնտեղ բաժանված են ջրով. նրանք, որոնք այլ անցում չունեն մեկից մյուսը, բացառությամբ կամրջի միջով: Այս օրինակում կան չորս այդպիսի բաժիններ՝ A, B, C, D: Այնուհետև պետք է տարբերակել, թե արդյոք դրանց թիվը Այս առանձին հատվածներին տանող կամուրջները զույգ են կամ կենտ: Այսպիսով, մեր դեպքում հինգ կամուրջները տանում են դեպի A հատվածը, և երեք կամուրջները դեպի մնացած հատվածները, այսինքն՝ առանձին հատվածներ տանող կամուրջների թիվը տարօրինակ է, և միայն սա բավարար է լուծելու համար։ Խնդիրը որոշվելուց հետո մենք կիրառում ենք հետևյալ կանոնը. եթե յուրաքանչյուր առանձին հատված տանող կամուրջների թիվը զույգ լիներ, ապա տվյալ շրջանցումը հնարավոր կլիներ, և միևնույն ժամանակ հնարավոր կլիներ սկսել այս շրջանցումը. եթե դրանք կենտ լինեին, քանի որ միայն մեկը չի կարող կենտ լինել, ապա նույնիսկ այդ դեպքում անցումը կարող էր ավարտվել, ինչպես սահմանված է, բայց միայն շրջանցման սկիզբը պետք է անպայման վերցվի այն երկու հատվածներից մեկից, որտեղ կենտ թվով կամուրջներ տանում. Եթե, ի վերջո, լինեին ավելի քան երկու հատվածներ, որոնց տանում են կենտ թվով կամուրջներ, ապա նման տեղաշարժն ընդհանրապես անհնար է... եթե այստեղ բերվեին այլ, ավելի լուրջ խնդիրներ, այս մեթոդը կարող էր ավելի մեծ օգուտ տալ և պետք է. մի անտեսեք»:

Վերոնշյալ կանոնի հիմնավորումը կարելի է գտնել Լ.Էյլերի նամակում իր ընկեր Էհլերին ուղղված նույն թվականի ապրիլի 3-ին: Ստորև կվերապատմենք այս նամակից մի հատված.

Մաթեմատիկոսը գրել է, որ անցումը հնարավոր է, եթե գետի պատառաքաղում չկան ավելի քան երկու տարածք, որին տանում են կենտ թվով կամուրջներ։ Որպեսզի դա ավելի հեշտ լինի պատկերացնել, մենք կջնջենք նկարի արդեն անցած կամուրջները: Հեշտ է ստուգել, ​​որ եթե մենք սկսենք շարժվել Էյլերի կանոններին համապատասխան, անցնենք մեկ կամուրջ և ջնջենք այն, ապա նկարը ցույց կտա մի հատված, որտեղ կրկին չկան երկուսից ավելի տարածքներ, որոնց տանում է տարօրինակ թվով կամուրջներ, և եթե կա. կենտ թվով կամուրջներ են, որոնցից մեկում մենք կտեղակայվենք: Այսպես շարունակելով առաջ գնալ՝ մեկ անգամ կանցնենք բոլոր կամուրջներով։

Քյոնիգսբերգ քաղաքի կամուրջների պատմությունը ժամանակակից շարունակություն ունի. Բացենք, օրինակ, մաթեմատիկայի դպրոցական դասագիրքը, որը խմբագրել է Ն.Յ. Վիլենկինա վեցերորդ դասարանի համար. Դրանում, 98-րդ էջում, ուշադրության և խելացիության զարգացում խորագրի ներքո մենք կգտնենք մի խնդիր, որն ուղղակիորեն կապված է այն խնդրի հետ, որը ժամանակին լուծել էր Էյլերը:

Խնդիր թիվ 569. Լճում կան յոթ կղզիներ, որոնք կապված են միմյանց հետ, ինչպես ցույց է տրված Նկար 1.2-ում: Ո՞ր կղզի պետք է տանի նավը ճանապարհորդներին, որպեսզի նրանք կարողանան անցնել յուրաքանչյուր կամուրջ և միայն մեկ անգամ: Ինչու՞ չի կարելի ճանապարհորդներին տեղափոխել կղզի: Ա?

Լուծում.Քանի որ այս խնդիրը նման է Քյոնիգսբերգի կամուրջների խնդրին, այն լուծելիս կօգտագործենք նաև Էյլերի կանոնը։ Արդյունքում ստանում ենք հետևյալ պատասխանը՝ նավը պետք է ճանապարհորդներին հասցնի կղզի Եկամ Ֆորպեսզի յուրաքանչյուր կամուրջը մեկ անգամ անցնեն։ Նույն Էյլերի կանոնից հետևում է, որ անհրաժեշտ շրջանցումն անհնար է, եթե այն սկսվում է կղզուց Ա.

Եզրափակելով, մենք նշում ենք, որ Քյոնիգսբերգի կամուրջների խնդիրը և նմանատիպ խնդիրները, դրանց ուսումնասիրության մի շարք մեթոդների հետ միասին, գործնական առումով մաթեմատիկայի շատ կարևոր ճյուղ են, որը կոչվում է գրաֆիկների տեսություն: Գրաֆիկների վերաբերյալ առաջին աշխատանքը պատկանել է Լ.Էյլերին և հայտնվել 1736 թվականին։ Հետագայում գրաֆիկների վրա աշխատել են Քյոնիգը (1774-1833), Համիլթոնը (1805-1865) և ժամանակակից մաթեմատիկոսներ Կ. Բերգեն, Օ. Օրեն, Ա. Զիկովը։

Գրաֆիկի տեսություն- դիսկրետ մաթեմատիկայի ամենածավալուն բաժիններից մեկը, որը լայնորեն օգտագործվում է տնտեսական և կառավարման խնդիրներ լուծելու, ծրագրավորման, քիմիայի, էլեկտրական սխեմաների նախագծման և ուսումնասիրության, կապի, հոգեբանության, հոգեբանության, սոցիոլոգիայի, լեզվաբանության և գիտելիքի այլ ոլորտներում: Գրաֆիկի տեսությունհամակարգված և հետևողականորեն ուսումնասիրում է գրաֆիկների հատկությունները, որոնք, կարելի է ասել, բաղկացած են կետերի և այդ կետերի միջև կապերը ներկայացնող գծերի շարքից: Գրաֆների տեսության հիմնադիրը համարվում է Լեոնհարդ Էյլերը (1707-1882), ով 1736 թվականին լուծեց Քյոնիգսբերգի կամուրջների այն ժամանակ հայտնի խնդիրը։

Գրաֆիկները կառուցված ենկոմպլեկտների վրա հարաբերություններ ցուցադրելու համար։ Թող, օրինակ, լինի հավաքածու Ա = {ա1 , ա 2 , ... աժդ)- շատ մարդիկ, և յուրաքանչյուր տարր կցուցադրվի որպես կետ: Մի փունջ Բ = {բ1 , բ 2 , ... բմ)- շատ կապեր (ուղիղ գծեր, աղեղներ, հատվածներ - դա դեռ կարևոր չէ): Նկարահանման հրապարակում ԱՏրված է այս հավաքածուի մարդկանց ծանոթության հարաբերությունները: Գրաֆիկի կառուցումկետերից և միացումներից: Հղումները կմիացնեն միմյանց ճանաչող մարդկանց զույգերը: Բնականաբար, որոշ մարդկանց ծանոթների թիվը կարող է տարբերվել այլ մարդկանց ծանոթների թվից, իսկ ոմանք կարող են ոչ ոքի չճանաչել (նման տարրերը կլինեն ոչ մեկի հետ չկապված կետեր): Այսպիսով, մենք ունենք գրաֆիկ:

Այն, ինչ մենք սկզբում անվանել ենք «կետեր», պետք է անվանել գրաֆիկի գագաթներ, իսկ այն, ինչ մենք անվանել ենք «կապեր», պետք է անվանել գրաֆիկի եզրեր:

Գրաֆիկների տեսությունը հաշվի չի առնում բազմությունների կոնկրետ բնույթը ԱԵվ Բ. Շատ տարբեր կոնկրետ խնդիրներ կան, որոնք լուծելիս կարելի է ժամանակավորապես մոռանալ հավաքածուների կոնկրետ բովանդակության և դրանց տարրերի մասին: Այս առանձնահատկությունը ոչ մի կերպ չի ազդում խնդրի լուծման առաջընթացի վրա՝ անկախ դրա դժվարությունից։ Օրինակ, երբ որոշվում է, թե արդյոք դա հնարավոր է մի կետից ահասնել կետին ե, շարժվելով միայն կետերը միացնող գծերով, կապ չունի՝ գործ ունենք մարդկանց, քաղաքների, թվերի հետ և այլն։ Բայց երբ խնդիրը լուծվում է, մենք ստանում ենք լուծում, որը ճիշտ է ցանկացած բովանդակության համար, որը մոդելավորվել է որպես գրաֆիկ: Հետևաբար, զարմանալի չէ, որ գրաֆիկների տեսությունը արհեստական ​​ինտելեկտի ստեղծման ամենահայտնի գործիքներից է. ի վերջո, արհեստական ​​ինտելեկտը զրուցակցի հետ կարող է քննարկել սիրո, երաժշտության կամ սպորտի, տարբեր խնդիրների լուծման հարցեր։ , և դա անում է առանց որևէ անցման (անջատման), առանց որի մարդը նման դեպքերում չի կարող առանց դրա։

Իսկ այժմ գրաֆիկի խիստ մաթեմատիկական սահմանումները։

Սահմանում 1.Այն կոչվում է գրաֆիկկամայական բնույթի օբյեկտների (գագաթների) և կապերի (եզրերի) համակարգ, որոնք կապում են այդ օբյեկտների որոշ զույգեր:

Սահմանում 2.Թող Վ– (ոչ դատարկ) գագաթների, տարրերի բազմություն v∈Վ- գագաթներ. Գրաֆիկ Գ = Գ(Վ) բազմաթիվ գագաթներով Վկա ձևի զույգերի որոշակի ընտանիք. ե = (ա, բ) , Որտեղ ա,բ∈Վ , նշելով, թե որ գագաթները մնում են միացված: Յուրաքանչյուր զույգ ե = (ա, բ) - գրաֆիկի եզրը: Մի փունջ U- շատ եզրեր եգրաֆիկ. Պիկեր աԵվ բ- եզրերի վերջնակետերը ե .

Գրաֆիկները որպես տվյալների կառուցվածք:Համակարգչային գիտության և տեղեկատվական տեխնոլոգիաների մեջ գրաֆիկների տեսության լայն կիրառումը պայմանավորված է վերը նշված սահմանումներին գրաֆի որպես տվյալների կառուցվածքի հայեցակարգի ավելացմամբ: Համակարգչային գիտության և տեղեկատվական տեխնոլոգիաների մեջ գրաֆիկը սահմանվում է որպես ոչ գծային տվյալների կառուցվածք: Այսպիսով, ի՞նչ է գծային տվյալների կառուցվածքը և ինչո՞վ են տարբերվում գրաֆիկները դրանցից: Գծային տվյալների կառուցվածքները բնութագրվում են նրանով, որ դրանք միացնում են տարրերը «պարզ հարևանության» տիպի հարաբերությունների միջոցով: Գծային տվյալների կառուցվածքներն են, օրինակ, զանգվածները, աղյուսակները, ցուցակները, հերթերը, կույտերը, տողերը: Ի հակադրություն, ոչ գծային տվյալների կառուցվածքներն այն կառուցվածքներն են, որոնցում տարրերը տեղակայված են հիերարխիայի տարբեր մակարդակներում և բաժանվում են երեք տեսակի՝ բնօրինակ, գեներացված և նմանատիպ: Այսպիսով, գրաֆիկը տվյալների ոչ գծային կառուցվածք է:

Գրաֆիկ բառը հունական ծագում ունի՝ «գրում եմ», «նկարագրում եմ» բառերից։ Այս հոդվածի սկզբից մենք գիտենք, թե կոնկրետ ինչ է նկարագրում գրաֆիկը. այն նկարագրում է հարաբերությունները: Այսինքն, ցանկացած գրաֆիկ նկարագրում է հարաբերությունները: Եվ հակառակը՝ ցանկացած հարաբերություն կարելի է բնութագրել որպես գրաֆիկ։

Գրաֆիկների տեսության հիմնական հասկացությունները

Պատահականության հայեցակարգը անհրաժեշտ է նաև գրաֆիկներով բազմաթիվ գործնական խնդիրներ լուծելու ալգորիթմներ մշակելիս: Օրինակ, դուք կարող եք ծանոթանալ ծրագրաշարի իրականացմանը Գրաֆիկի խորություն-առաջին անցում, որը ներկայացված է անկման մատրիցով. Գաղափարը պարզ է. դուք կարող եք շարժվել միայն եզրերով միացված գագաթներով: Եվ եթե որոշ արժեքներ վերագրվում են եզրերին («կշեռքներ», առավել հաճախ թվերի տեսքով, այդպիսի գրաֆիկները կոչվում են կշռված կամ պիտակավորված), ապա կարող են լուծվել բարդ կիրառական խնդիրներ, որոնցից մի քանիսը նշված են վերջին պարբերությունում: այս դասի.

Գրաֆների տեսության դասական խնդիրները և դրանց լուծումները

Գրաֆների տեսության և գրաֆիկների կիրառման վերաբերյալ աշխատանքի առաջին հրապարակված օրինակներից է «Քյոնիգսբերգի կամուրջների խնդրի» (1736) աշխատությունը, որը հեղինակել է 18-րդ դարի նշանավոր մաթեմատիկոս Լեոնհարդ Էյլերը։ Խնդիրը պարունակում է գետ, կղզիներ, որոնք ողողվում են այս գետով և մի քանի կամուրջներ։ Խնդրի հարցը՝ հնարավո՞ր է որոշակի կետ թողնելուց հետո յուրաքանչյուր կամուրջ անցնել միայն մեկ անգամ և վերադառնալ սկզբնակետ։ (ստորև նկարը)

Խնդիրը կարելի է մոդելավորել հետևյալ կերպ. յուրաքանչյուր հողատարածքին կցվում է մեկ կետ, և երկու կետ միացված են գծով, եթե և միայն այն դեպքում, եթե համապատասխան հողատարածքները միացված են կամրջով (ներքևի նկարը, միացնող գծերը գծված են կետագծերով) . Այսպիսով, գրաֆիկը կառուցված է:

Խնդրի հարցին Էյլերի պատասխանը հետևյալն է. Եթե ​​այս խնդիրը դրական լուծում ունենար, ապա ստացված գրաֆիկում կլիներ փակ ճանապարհ, որն անցնում էր եզրերով և կպարունակեր յուրաքանչյուր եզր միայն մեկ անգամ։ Եթե ​​այդպիսի ճանապարհ կա, ապա յուրաքանչյուր գագաթ պետք է ունենա միայն զույգ թվով եզրեր։ Բայց ստացված գրաֆիկն ունի գագաթներ, որոնք ունեն կենտ թվով եզրեր: Հետեւաբար, խնդիրը դրական լուծում չունի։

Ըստ հաստատված ավանդույթի՝ էյլերյան գրաֆիկը այն գրաֆիկն է, որտեղ հնարավոր է անցնել բոլոր գագաթները և միևնույն ժամանակ մեկ եզրով անցնել միայն մեկ անգամ։ Դրանում յուրաքանչյուր գագաթ պետք է ունենա միայն զույգ թվով եզրեր։ Էյլերի գրաֆիկների վրա միջին դժվարության խնդիր կա «Գրաֆիկների հիմնական տեսակները» նյութում։

1847 թվականին Կիրխհոֆը մշակեց ծառերի տեսությունը՝ լուծելու գծային հանրահաշվական հավասարումների համաժամանակյա համակարգը՝ թույլ տալով գտնել հոսանքի արժեքը յուրաքանչյուր հաղորդիչում (աղեղ) և էլեկտրական շղթայի յուրաքանչյուր շղթայում։ Վերցվելով դիմադրություններ, կոնդենսատորներ, ինդուկտացիաներ և այլն պարունակող էլեկտրական սխեմաներից և սխեմաներից, նա դիտարկեց համապատասխան կոմբինատոր կառուցվածքները, որոնք պարունակում են միայն գագաթներ և կապեր (եզրեր կամ աղեղներ), և միացումների համար կարիք չկա հաշվի առնել, թե ինչ տեսակի էլեկտրական տարրեր: դրանք համապատասխանում են. Այսպիսով, Կիրխհոֆը յուրաքանչյուր էլեկտրական սխեման փոխարինեց համապատասխան գրաֆիկով և ցույց տվեց, որ հավասարումների համակարգը լուծելու համար անհրաժեշտ չէ առանձին դիտարկել էլեկտրական շղթայի գրաֆիկի յուրաքանչյուր ցիկլը։

Քեյլին 1858 թվականին, օրգանական քիմիայի զուտ գործնական խնդիրների վրա աշխատելիս, հայտնաբերեց գրաֆիկների կարևոր դաս, որը կոչվում էր ծառեր։ Նա փորձեց թվարկել հագեցած ածխաջրածինների իզոմերները՝ ածխածնի ատոմների տրված քանակով։ Քեյլին նախ աբստրակտ ձևակերպեց խնդիրը՝ գտե՛ք բոլոր ծառերի թիվը էջգագաթներ, որոնցից յուրաքանչյուրն ունի գագաթներ 1-ին և 4-րդ աստիճաններով: Նա չկարողացավ անմիջապես լուծել այս խնդիրը, և նա սկսեց փոխել դրա ձևակերպումը այնպես, որ հնարավոր լինի լուծել նոր թվային խնդիր.

• արմատավորված ծառեր (որոնցում ընտրված է գագաթներից մեկը);
• բոլոր ծառերը;
• ծառեր, որոնց գագաթային աստիճանները չեն գերազանցում 4-ը.
• ծառեր, որոնց գագաթային աստիճանները 1 և 4 են (խնդիրի ձևակերպում քիմիայից):

Հիմնական հասկացություններն ամրապնդելու համար գրաֆիկական խնդիրներ

Օրինակ 1.Թող Ա- 1, 2, 3 թվերի հավաքածու: Ա= (1, 2, 3) . Կառուցեք գրաֆիկ՝ հարաբերությունները ցուցադրելու համար»

Լուծում. Ակնհայտ է, որ 1, 2, 3 թվերը պետք է ներկայացվեն որպես գրաֆիկի գագաթներ: Այնուհետեւ գագաթների յուրաքանչյուր զույգ պետք է միացված լինի մեկ եզրով: Լուծելով այս խնդիրը՝ մենք հասանք գրաֆիկների տեսության այնպիսի հիմնական հասկացությունների, ինչպիսիք են ուղղորդված և չուղղորդված գրաֆիկներ. Չուղղորդված գրաֆիկներն այն գրաֆիկներն են, որոնց եզրերը ուղղություն չունեն: Կամ, ինչպես ասում են նույնիսկ ավելի հաճախ, եզրի երկու ծայրերի հերթականությունը էական չէ։ Փաստորեն, այս դասի հենց սկզբում կառուցված և մարդկանց միջև ծանոթության հարաբերությունները ներկայացնող գրաֆիկը եզրային ուղղությունների կարիք չունի, քանի որ կարելի է պնդել, որ «թիվ 1-ը» նույն չափով ծանոթ է «թիվ 2-ին»: որպես «թիվ 2 անձ» «թիվ 1 անձի» հետ: Մեր ներկայիս օրինակում մի թիվ փոքր է մյուսից, բայց ոչ հակառակը: Հետևաբար, գրաֆիկի համապատասխան եզրը պետք է ունենա ուղղություն, որը ցույց է տալիս, թե որ թիվն է փոքր մյուսից: Այսինքն՝ եզրերի ծայրերի հերթականությունը նշանակալի է։ Նման գրաֆիկը (ուղղություն ունեցող եզրերով) կոչվում է ուղղորդված գրաֆիկ կամ երկգրաֆ։

Այսպիսով, մեր բազմության մեջ Աթիվ 1-ը փոքր է 2-ից և 3-ից, իսկ 2-ը փոքր է 3-ից: Մենք ստանում ենք հետևյալ գրաֆիկը.

Օրինակ 2.Թող Ա- 2, 4, 6, 14 թվերի հավաքածու: Ա= (2, 4, 6, 14) . Ստեղծեք գրաֆիկ՝ այս բազմության վրա «բաժանելի է» կապը ցուցադրելու համար:

Լուծում. Այս օրինակում եզրերի մի մասը կունենա ուղղություն, իսկ որոշները՝ ոչ, այսինքն՝ մենք կառուցում ենք խառը գրաֆիկ. Թվարկենք բազմության հարաբերությունները՝ 4-ը բաժանվում է 2-ի, 6-ը բաժանվում է 2-ի, 14-ը բաժանվում է 2-ի, և այս բազմությունից յուրաքանչյուր թիվ բաժանվում է ինքն իրեն։ Այս հարաբերությունը, այսինքն, երբ թիվն ինքն իրեն բաժանվում է, կցուցադրվի եզրերի տեսքով, որոնք կապում են գագաթն իրեն։ Նման եզրերը կոչվում են loops. Այս դեպքում օղակին ուղղություն տալու կարիք չկա։ Այսպիսով, մեր օրինակում կան երեք կանոնավոր ուղղորդված եզրեր և չորս օղակներ: Մենք ստանում ենք հետևյալ գրաֆիկը.

Օրինակ 3.Թող տրված հավաքածուները Ա= (α, β, γ) և Բ= (a, b, c) . Կառուցեք գրաֆիկ՝ «Բազմությունների դեկարտյան արտադրյալ» կապը ցուցադրելու համար:

Լուծում. Ինչպես հայտնի է սահմանումից Կոմպլեկտների դեկարտյան արտադր, նույն հավաքածուի տարրերի պատվիրված հավաքածուներ չկան։ Այսինքն, մեր օրինակում դուք չեք կարող հունարեն տառերը հունարենով, իսկ լատիներենը՝ լատիներենով համատեղել։ Այս փաստը ցուցադրվում է որպես երկկողմանի գրաֆիկ, այսինքն՝ մեկը, որի գագաթները բաժանված են երկու մասի, որպեսզի նույն մասին պատկանող գագաթները միմյանց հետ կապված չլինեն։ Մենք ստանում ենք հետևյալ գրաֆիկը.

Օրինակ 4.Անշարժ գույքի գործակալությունում աշխատում են մենեջերներ Իգորը, Սերգեյը և Պյոտրը։ O1, O2, O3, O4, O5, O6, O7, O8 օբյեկտները սպասարկվում են: Կառուցեք գրաֆիկ՝ «Իգորն աշխատում է O4, O7 օբյեկտների հետ», «Սերգեյն աշխատում է O1, O2, O3, O5, O6 օբյեկտների հետ», «Պետերն աշխատում է O8 օբյեկտի հետ» հարաբերությունները ցուցադրելու համար:

Լուծում. Այս հարաբերությունները ցուցադրող գրաֆիկը նույնպես երկկողմանի կլինի, քանի որ կառավարիչը չի աշխատում մենեջերի հետ, իսկ օբյեկտը չի աշխատում օբյեկտի հետ: Այնուամենայնիվ, ի տարբերություն նախորդ օրինակի, գրաֆիկը ուղղորդված կլինի: Իրականում, օրինակ, Իգորն աշխատում է O4 օբյեկտի հետ, իսկ O4 օբյեկտը չի աշխատում Իգորի հետ: Հաճախ, երբ հարաբերությունների նման հատկությունն ակնհայտ է, եզրերին ուղղություն տալու անհրաժեշտությունը կարող է թվալ որպես «մաթեմատիկական հիմարություն»։ Բայց այնուամենայնիվ, և դա բխում է մաթեմատիկայի խիստ բնույթից, եթե հարաբերությունները միակողմանի են, ապա պետք է ուղղություններ տալ եզրերին։ Հարաբերական ծրագրերում այս խստությունը վճարում է, օրինակ, պլանավորման համար նախատեսված ծրագրերում, որտեղ օգտագործվում են նաև գրաֆիկներ, և գագաթների և եզրերի երկայնքով երթուղին պետք է անցնի խստորեն տվյալ ուղղությամբ: Այսպիսով, մենք ստանում ենք հետևյալ ուղղորդված երկկողմանի գրաֆիկը.

Եվ կրկին թվերով օրինակներ։

Օրինակ 5.Թող տրվի հավաքածու Գ = {2, 3, 5, 6, 15, 18} . Կառուցեք գրաֆիկ, որն իրականացնում է բոլոր զույգ թվերը սահմանող հարաբերություն աԵվ բշատերից Գ, որի դեպքում երկրորդ տարրը առաջինի վրա բաժանելիս ստանում ենք գործակից, որը 1-ից մեծ է։

Լուծում. Այս հարաբերությունները ցուցադրող գրաֆիկը կողմնորոշված ​​կլինի, քանի որ պայմանը պարունակում է երկրորդ և առաջին տարրերի հիշատակում, այսինքն՝ եզրը կուղղվի առաջին տարրից երկրորդ: Այստեղից պարզ է դառնում, թե որ տարրն է առաջինը, որը՝ երկրորդը։ Ավելացնենք նաև որոշ տերմինաբանություն՝ կողմնորոշված ​​եզրերը սովորաբար կոչվում են աղեղներ։ Մեր գրաֆիկում կլինի 7 աղեղ. ե1 = (3, 15) , ե2 = (3, 18) , ե3 = (5, 15) , ե4 = (3, 6) , ե5 = (2, 18) , ե6 = (6, 18) , ե7 = (2, 6) . Այս օրինակում գրաֆիկի եզրերը (աղեղները) պարզապես համարակալված են, բայց սերիական համարները միակ բանը չեն, որ կարող են վերագրվել աղեղին։ Աղեղին կարող են վերագրվել նաև կշեռքներ, ինչը նշանակում է, օրինակ, բեռը մի կետից մյուսը ուղարկելու արժեքը: Բայց աղեղային կշիռներին կծանոթանանք ավելի ուշ և ավելի մանրամասն։ Այսպիսով, մենք ստանում ենք հետևյալ ուղղորդված գրաֆիկը.

Ինչպես արդեն գիտենք տեսական ներածական մասից, գրաֆիկների տեսությունը հաշվի չի առնում բազմությունների սպեցիֆիկ բնույթը և նույն գրաֆիկի օգնությամբ հնարավոր է սահմանել հարաբերություններ շատ տարբեր բովանդակությամբ բազմությունների վրա։ Այսինքն, հենց այս բովանդակությունը կարող է վերացվել առաջադրանք մոդելավորելիս: Եկեք անցնենք օրինակների, որոնք ցույց են տալիս գրաֆիկների տեսության այս ուշագրավ հատկությունը:

Օրինակ 6. 3 X 3 չափսերով շախմատի խաղատախտակի վրա դրված են երկու սպիտակ և երկու սև ասպետներ, ինչպես ցույց է տրված ստորև նկարում:

Հնարավո՞ր է ասպետներին տեղափոխել ստորև ներկայացված նկարում պատկերված վիճակ՝ չմոռանալով, որ երկու խաղաքարերը չեն կարող լինել նույն քառակուսու վրա։

Լուծում. Կառուցված գրաֆիկում գագաթների զույգերը կկապվեն «ասպետի շարժում» կապով: Այսինքն՝ մի գագաթն այն մեկն է, որտեղից ասպետը հեռացել է, իսկ մյուսը՝ այն, որին հասել է, և «r» տառի միջանկյալ բջիջը կլինի այս հարաբերությունից դուրս։ Մենք ստանում ենք հետևյալ գրաֆիկը.

Եվ այնուամենայնիվ դիզայնը ծանրաբեռնված էր։ Դրանում տեսանելի են շախմատի տախտակի բջիջները, և գրաֆիկի շատ եզրեր հատվում են: Հնարավո՞ր է վերացարկվել շախմատի տախտակի ֆիզիկական տեսքից և ավելի պարզ պատկերացնել հարաբերությունները։ Պարզվում է՝ դա հնարավոր է։ Նոր գրաֆիկում հարևան գագաթները կլինեն այն գագաթները, որոնք կապված են «ասպետի քայլ» հարաբերությունների հետ, և ոչ թե հարևանները շախմատի տախտակի վրա (ստորև նկարը):

Այժմ հեշտ է տեսնել, որ այս խնդրի պատասխանը բացասական է։ Նախնական վիճակում երկու սպիտակ ասպետների միջև չկա սև ասպետ, բայց վերջնական վիճակում պետք է լինի այս սև ասպետը: Գրաֆիկի եզրերը տեղադրվում են այնպես, որ երկու հարևան ասպետներ չկարողանան ցատկել միմյանց վրայով:

Օրինակ 7.Խնդիրը գայլի, այծի և կաղամբի մասին. Գետի մի ափին կան մարդ (H), նավակ, գայլ (V), այծ (Kz) և կաղամբ (Kp): Մարդը և տեղափոխվող առարկաներից ոչ ավելին միաժամանակ կարող են լինել նավակի մեջ։ Մարդը պետք է բոլոր առարկաները տեղափոխի մյուս կողմ՝ պահպանելով պայմանը՝ գայլը այծի հետ չպետք է մնա առանց հսկողության, իսկ այծը՝ կաղամբով։

Լուծում. Կառուցված գրաֆիկում գագաթները կոնֆիգուրացիաներ են, իսկ եզրերը՝ «միացում մեկ նավով զբոսանքով» կապը կոնֆիգուրացիաների միջև: Կազմաձևը վերաբերում է առարկաների դասավորությանը սկզբնական ափին և հակառակ ափին: Յուրաքանչյուր կոնֆիգուրացիա ցուցադրվում է որպես ( Ա|Բ), Որտեղ Ա- առարկաներ, որոնք գտնվում են սկզբնական ափին, և Բ- հակառակ ափին գտնվող օբյեկտներ. Հետևաբար, սկզբնական կոնֆիգուրացիան հետևյալն է. (PMCpKz| ) . Օրինակ, այծը մյուս կողմ տեղափոխելուց հետո կոնֆիգուրացիան կլինի (VKp|ՉԿզ) . Վերջնական կոնֆիգուրացիան միշտ է ( |PMCpKz) . Այժմ մենք կարող ենք կառուցել գրաֆիկ՝ արդեն իմանալով, թե ինչ են նշանակում գագաթներն ու եզրերը.

Գրաֆիկի գագաթները դնենք այնպես, որ եզրերը չհատվեն, իսկ հարևան գագաթները նրանք են, որոնք կապված են գրաֆիկի վրա: Այնուհետև շատ ավելի հեշտ կլինի տեսնել հարաբերությունները (նկարը մեծացնելու համար ձախ սեղմեք դրա վրա).

Ինչպես տեսնում ենք, կան երկու տարբեր շարունակական երթուղիներ՝ սկզբնական կոնֆիգուրացիայից մինչև վերջնական: Հետևաբար, խնդիրն ունի երկու տարբեր լուծումներ (և երկուսն էլ ճիշտ են):

Գրաֆիկների տեսությունը և ժամանակակից կիրառական կարևորագույն խնդիրները

Գրաֆների տեսության հիման վրա մշակվել են կիրառական խնդիրների լուծման մեթոդներ, որոնցում շատ բարդ համակարգերը մոդելավորվում են գրաֆիկների տեսքով։ Այս մոդելներում հանգույցները պարունակում են առանձին բաղադրիչներ, իսկ եզրերը ներկայացնում են բաղադրիչների միջև կապը: Սովորաբար, կշռված գրաֆիկներն օգտագործվում են տրանսպորտային ցանցերի, հերթագրման համակարգերի և ցանցի պլանավորման մոդելավորման համար: Մենք արդեն խոսել ենք դրանց մասին, սրանք գծապատկերներ են, որոնցում կշիռներ են նշանակվում կամարներին:

Ծառի գրաֆիկները օգտագործվում են, օրինակ, կառուցելու համար որոշման ծառեր(ծառայում է ռիսկերի վերլուծության, անորոշության պայմաններում հնարավոր օգուտների և վնասների վերլուծության համար): Օգտագործելով գրաֆիկների տեսությունը՝ մշակված և այլ բազմաթիվ մաթեմատիկական մոդելներկոնկրետ առարկայական ոլորտներում խնդիրներ լուծելու համար:

Գրաֆիկները և հոսքի խնդիրը

Խնդրի ձևակերպում. Գոյություն ունի ջրատարների համակարգ, որը ներկայացված է ստորև բերված նկարում ներկայացված գրաֆիկով:

Գրաֆիկի յուրաքանչյուր աղեղը ներկայացնում է խողովակ: Աղեղների (կշեռքների) վերևում գտնվող թվերը խողովակի հզորությունն են: Հանգույցները խողովակների միացման վայրերն են: Ջուրը խողովակներով հոսում է միայն մեկ ուղղությամբ. Հանգույց Ս- ջրի աղբյուր, հանգույց Տ- պաշար. Պահանջվում է առավելագույնի հասցնել ջրի ծավալը, որը հոսում է աղբյուրից դեպի արտահոսք:

Հոսքի խնդիրը լուծելու համար կարող եք օգտագործել Ford-Fulkerson մեթոդը: Մեթոդի գաղափարը. առավելագույն հոսքի որոնումն իրականացվում է քայլերով: Ալգորիթմի սկզբում հոսքը սահմանվում է զրոյի: Յուրաքանչյուր հաջորդ քայլում հոսքի արժեքը մեծանում է, ինչի համար որոնվում է լրացուցիչ ուղի, որով հասնում է լրացուցիչ հոսքը: Այս քայլերը կրկնվում են այնքան ժամանակ, քանի դեռ կան լրացուցիչ ուղիներ: Խնդիրը հաջողությամբ կիրառվել է տարբեր բաշխված համակարգերում՝ էլեկտրամատակարարման համակարգ, կապի ցանց, երկաթուղային համակարգ և այլն։

Գրաֆիկները և ցանցի պլանավորումը

Բազմաթիվ աշխատանքներից բաղկացած բարդ գործընթացների պլանավորման խնդիրներում, որոնցից մի քանիսը կատարվում են զուգահեռ, իսկ որոշները հաջորդաբար, լայնորեն կիրառվում են կշռված գրաֆիկները, որոնք հայտնի են որպես PERT ցանցեր:

PERT - Ծրագրի (նախագծի) գնահատման և վերանայման տեխնիկա - ծրագրերի (նախագծերի) գնահատման և վերլուծության տեխնիկա, որն օգտագործվում է նախագծերի կառավարման մեջ:

PERT ցանցը կշռված ացիկլիկ ուղղորդված գրաֆիկ է, որտեղ յուրաքանչյուր աղեղ ներկայացնում է աշխատանք (գործողություն, գործողություն), և աղեղի կշիռը այն ավարտելու համար պահանջվող ժամանակն է։

Եթե ​​ցանցում կամարներ կան ( ա, բ) Եվ ( բ, գ), ապա աղեղով ներկայացված աշխատանքը ( ա, բ) պետք է ավարտվի նախքան աղեղով ներկայացված աշխատանքը ( բ, գ) . Յուրաքանչյուր գագաթ ( vi)ներկայացնում է ժամանակի այն կետը, որով ամբողջ աշխատանքը, որը սահմանվում է գագաթով ավարտվող աղեղներով ( vi).

Այսպիսի սյունակում.

• մեկ գագաթը, որը չունի նախորդներ, որոշում է աշխատանքի մեկնարկի ժամանակը.
• մեկ գագաթը, որը չունի հետևորդներ, համապատասխանում է ժամանակի այն պահին, երբ ավարտվում է աշխատանքների ամբողջությունը։

Գրաֆիկի այս գագաթների միջև առավելագույն երկարության ուղին (աշխատանքային գործընթացի սկզբից մինչև վերջ) կոչվում է կրիտիկական ուղի։ Աշխատանքի ամբողջ համալիրն ավարտելու համար պահանջվող ժամանակը նվազեցնելու համար անհրաժեշտ է գտնել աշխատանք, որը գտնվում է կրիտիկական ուղու վրա և կրճատել դրա տևողությունը, օրինակ՝ ներգրավելով լրացուցիչ կատարողներ, մեխանիզմներ և նոր տեխնոլոգիաներ:

«Գրաֆիկի տեսություն» ամբողջ բլոկը

Նյութը՝ Վիքիպեդիայից՝ ազատ հանրագիտարանից

Գրաֆիկի տեսություն- դիսկրետ մաթեմատիկայի մի ճյուղ, որն ուսումնասիրում է գրաֆիկների հատկությունները: Ընդհանուր իմաստով, գրաֆիկը ներկայացված է որպես բազմություն գագաթները(հանգույցներ) միացված կողիկներ. Խիստ սահմանման մեջ նման զույգ բազմությունները կոչվում են գրաֆիկ։ $G\; =\; (V,\; E)$, Որտեղ $Վ$ցանկացած հաշվելի բազմության ենթաբազմություն է, և $Ե$- ենթաբազմություն $V\backslash \; անգամ\; V$.

Գրաֆիկների տեսությունը կիրառություն է գտնում, օրինակ, աշխարհագրական տեղեկատվական համակարգերում (GIS): Գագաթներ են համարվում գոյություն ունեցող կամ նոր նախագծված տները, շինությունները, բլոկները և այլն, իսկ եզրեր են համարվում դրանք միացնող ճանապարհները, կոմունալ ցանցերը, էլեկտրահաղորդման գծերը և այլն։ Նման գրաֆիկի վրա կատարված տարբեր հաշվարկների օգտագործումը թույլ է տալիս, օրինակ, գտնել ամենակարճ շրջանցման երթուղին կամ մոտակա մթերային խանութը կամ պլանավորել օպտիմալ երթուղին։

Գրաֆիկների տեսությունը պարունակում է մեծ թվով չլուծված խնդիրներ և դեռևս չապացուցված վարկածներ։

Գրաֆիկների տեսության պատմություն

Լեոնարդ Էյլերը համարվում է գրաֆիկների տեսության հիմնադիրը։ 1736 թվականին նա իր նամակներից մեկում ձևակերպել և առաջարկել է Քյոնիգսբերգի յոթ կամուրջների խնդրի լուծումը, որը հետագայում դարձել է գրաֆիկների տեսության դասական խնդիրներից մեկը։

Գրաֆիկների տեսության տերմինաբանություն

Գրաֆիկների ներկայացում հարթության վրա

Գծագրերում գրաֆիկները պատկերելիս առավել հաճախ օգտագործվում է հետևյալ նշագրման համակարգը. գրաֆիկի գագաթները պատկերվում են որպես կետեր կամ գագաթի իմաստը նշելիս ուղղանկյուններ, օվալներ և այլն, որտեղ գագաթի իմաստը բացահայտվում է ներսում: նկարը (ալգորիթմների հոսքային գծապատկերների գրաֆիկները): Եթե ​​գագաթների միջև կա եզր, ապա համապատասխան կետերը (ձևերը) միացված են գծով կամ աղեղով։ Ուղղորդված գրաֆիկի դեպքում աղեղները փոխարինվում են սլաքներով կամ հստակ նշվում է եզրի ուղղությունը: Երբեմն եզրագծի կողքին տեղադրվում են բացատրական մակագրություններ՝ բացահայտելով եզրի նշանակությունը, օրինակ՝ վերջավոր վիճակի մեքենաների անցումային գրաֆիկներում։ Կան հարթ և ոչ հարթ գրաֆիկներ։ Հարթական գրաֆիկը այն գրաֆիկն է, որը կարելի է պատկերել նկարում (հարթության վրա) առանց հատվող եզրերի (ամենապարզը եռանկյունն է կամ զույգ միացված գագաթները), հակառակ դեպքում գրաֆիկը ոչ հարթ է։ Այն դեպքում, երբ գրաֆիկը չի պարունակում ցիկլեր (պարունակում է առնվազն մեկ ուղի մի ժամանակեզրերի և գագաթների անցում սկզբնական գագաթին վերադարձով), այն սովորաբար կոչվում է «ծառ»: Գրաֆիկների տեսության մեջ ծառերի կարևոր տեսակներն են երկուական ծառերը, որտեղ յուրաքանչյուր գագաթ ունի մեկ մուտքային եզր և ուղիղ երկու ելքային, կամ վերջավոր է, չունի ելքային եզրեր և պարունակում է մեկ արմատային գագաթ առանց մուտքային եզրերի:

Գրաֆիկի պատկերը չպետք է շփոթել հենց գրաֆիկի հետ (վերացական կառուցվածք), քանի որ մեկից ավելի գրաֆիկական ներկայացում կարող է կապված լինել մեկ գրաֆիկի հետ: Պատկերը նախատեսված է միայն ցույց տալու, թե գագաթների որ զույգերն են միացված եզրերով, որոնք՝ ոչ: Հաճախ գործնականում դժվար է պատասխանել այն հարցին, թե երկու պատկերները նույն գրաֆիկի մոդելներ են, թե ոչ (այլ կերպ ասած՝ պատկերներին համապատասխանող գրաֆիկները իզոմորֆ են)։ Կախված առաջադրանքից, որոշ պատկերներ կարող են ավելի շատ պարզություն տալ, քան մյուսները:

Գրաֆների տեսության որոշ խնդիրներ

• Քյոնիգսբերգի խնդրի յոթ կամուրջը գրաֆների տեսության առաջին արդյունքներից մեկն է, որը հրապարակվել է Էյլերի կողմից:
• Չորս գույնի խնդիրը ձևակերպվել է 1852 թվականին, բայց ոչ դասական ապացույցը ստացվել է միայն 1976 թվականին (4 գույնը բավարար է քարտեզի համար գնդի (հարթության) վրա)։
• Ճանապարհորդող վաճառողի խնդիրը ամենահայտնի NP-ամբողջական խնդիրներից մեկն է:
• Կլիկի խնդիրը մեկ այլ NP-ամբողջական խնդիր է:
• Գտնելով նվազագույն ընդգրկող ծառը:
• Գրաֆիկի իզոմորֆիզմ - հնարավո՞ր է մեկ գրաֆիկի գագաթները վերահամարակալելով ստանալ մյուսը:
• Գրաֆիկի հարթություն - հնարավո՞ր է գրաֆիկը պատկերել հարթության վրա՝ առանց եզրերի հատումների (կամ շերտերի նվազագույն քանակով, որն օգտագործվում է տպագիր տպատախտակների կամ միկրոսխեմաների տարրերի փոխկապակցումները հետագծելիս):

Գրաֆների տեսության կիրառում

տես նաեւ

Գրեք ակնարկ «Գրաֆիկի տեսություն» հոդվածի մասին

Նշումներ

գրականություն

• Դիստել Ռ.Գրաֆի տեսություն Տրանս. անգլերենից - Նովոսիբիրսկ: Մաթեմատիկայի ինստիտուտի հրատարակչություն, 2002 թ. - 336 էջ. ISBN 5-86134-101-X.
• Դիզել Ռ.. - NY: Springer-Verlag, 2005. - P. 422:
• Բասաքեր Ռ., Սաատի Թ.
• Բելով Վ.Վ., Վորոբիև Է.Մ., Շատալով Վ.Է.Գրաֆիկի տեսություն. - Մ.: Ավելի բարձր: դպրոց, 1976. - P. 392:
• Պերճ Կ.
• Էմելիչև Վ.Ա., Մելնիկով Օ.Ի., Սարվանով Վ.Ի., Տիշկևիչ Ռ.Ի.Դասախոսություններ գրաֆիկների տեսության վերաբերյալ. M.: Nauka, 1990. 384 p. (Խմբ. 2, վերանայված M.: URSS, 2009. 392 p.)
• Զիկով Ա.Ա.. - Մ.: «Համալսարանական գիրք», 2004. - P. 664. - ISBN 5-9502-0057-8:(M.: Nauka, 1987. 383c.)
• Տոպոլոգիայի և գրաֆիկների տեսության քիմիական կիրառությունները. Էդ. R. King. Պեր. անգլերենից Մ.: Միր, 1987:
• Կիրսանով Մ.Ն.Գրաֆիկները Maple-ում: M.: Fizmatlit, 2007. 168 p. vuz.exponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Քրիստոֆիդես Ն.
• Cormen T.H. et al.Մաս VI. Գրաֆիկների հետ աշխատելու ալգորիթմներ // Ալգորիթմներ՝ կառուցում և վերլուծություն = Ալգորիթմների ներածություն. - 2-րդ հրատ. - M.: Williams, 2006. - P. 1296. - ISBN 0-07-013151-1:
• Հանքաքար Օ.. - 2-րդ հրատ. - M.: Գիտություն, 1980. - P. 336:
• Սալի Վ. Ն. Բոգոմոլով Ա.Մ.. - Մ.: Ֆիզիկա և մաթեմատիկական գրականություն, 1997. - ISBN 5-02-015033-9:
• Սվամի Մ., Թուլասիրաման Կ.
• Թաթ Վ.
• Վիլսոն Ռ.
• Հարարի Ֆ.. - Մ.: Միր, 1973:(Ed. 3, M.: KomKniga, 2006. - 296 p.)
• Հարարի Ֆ., Պալմեր Է.. - Աշխարհ, 1977 թ.
• Սերգեյ Մելնիկով// Գիտություն և կյանք. - 1996. - Համար. 3. - էջ 144-145։Հոդվածը Գուստավ Սիմոնսի հորինած Sim գրաֆիկական խաղի մասին է։

Հղումներ

• Ծրագիր, որն օգտագործողին տրամադրում է գործիքների և մեթոդների լայն շրջանակ՝ գրաֆիկներում տեղեկատվություն պատկերացնելու և որոնելու համար։

Դասական վերլուծություն Ֆունկցիայի տեսություն Դիֆերենցիալ և ինտեգրալ հավասարումներ

Գրաֆիկների տեսությունը բնութագրող հատված

Բայց մինչ նա կավարտի այս խոսքերը, արքայազն Անդրեյը, զգալով, որ ամոթի արցունքներն ու զայրույթը բարձրանում էին կոկորդում, արդեն ցատկում էր ձիուց և վազում դեպի դրոշակը։
- Տղե՛րք, առաջ գնացե՛ք։ – բղավեց նա մանկաբար:
"Ահա այն!" մտածեց արքայազն Անդրեյը, բռնելով դրոշակաձողը և հաճույքով լսելով փամփուշտների սուլոցը, ակնհայտորեն ուղղված էր հենց իրեն: Մի քանի զինվոր ընկան։
- Ուռա՜ - բղավեց արքայազն Անդրեյը, հազիվ ծանր դրոշակը ձեռքում պահելով և առաջ վազեց անկասկած վստահությամբ, որ ամբողջ գումարտակը կվազի իր հետևից:
Իսկապես, նա միայնակ մի քանի քայլ վազեց։ Մի զինվոր ճամփա ընկավ, հետո մյուսը, և ամբողջ գումարտակը բղավեց «Ուռա՛»։ առաջ վազեց և շրջանցեց նրան: Գումարտակի ենթասպան վազեց և վերցրեց արքայազն Անդրեյի ձեռքում ծանրությունից դողացող դրոշը, բայց անմիջապես սպանվեց։ Արքայազն Անդրեյը կրկին բռնեց դրոշը և, այն ձողով քարշ տալով, գումարտակի հետ փախավ: Առջևից նա տեսավ մեր հրետանավորներին, որոնցից մի քանիսը կռվեցին, մյուսները թողեցին թնդանոթները և վազեցին դեպի իրեն; նա նաև տեսել է ֆրանսիացի հետևակային զինվորներին, ովքեր բռնել են հրետանային ձիերը և շրջել հրացանները: Արքայազն Անդրեյն ու նրա գումարտակն արդեն 20 քայլ հեռու էին հրացաններից։ Նա լսում էր իր գլխավերևում գնդակների անդադար սուլոցը, և զինվորները անընդհատ հառաչում էին և ընկնում նրանից աջ ու ձախ։ Բայց նա չնայեց նրանց. նա նայեց միայն այն ամենին, ինչ կատարվում էր իր դիմաց՝ մարտկոցի վրա։ Նա պարզ տեսավ, որ կարմիր մազերով հրետանու մի կերպար՝ շակոյով թակել է մի կողմից՝ մի կողմից դրոշ քաշելով, մինչդեռ ֆրանսիացի զինվորը մյուս կողմից դրոշն էր քաշում դեպի իրեն։ Արքայազն Անդրեյն արդեն պարզորոշ տեսնում էր այս երկու մարդկանց դեմքերի շփոթված և միևնույն ժամանակ դառն արտահայտությունը, որոնք, ըստ երևույթին, չէին հասկանում, թե ինչ են անում։
"Ինչ են նրանք անում? - մտածեց արքայազն Անդրեյը ՝ նայելով նրանց. - ինչու՞ կարմիր մազերով հրետանավորը չի վազում, երբ զենք չունի: Ինչո՞ւ ֆրանսիացին դանակով չի հարվածում նրան. Մինչ կհասնի նրան, ֆրանսիացին կհիշի ատրճանակը և կսպանի նրան»:
Իսկապես, մեկ այլ ֆրանսիացի, իր օգտին ատրճանակով, վազեց դեպի մարտիկները, և պետք է որոշվեր կարմրահեր հրետանավորի ճակատագիրը, որը դեռ չէր հասկանում, թե ինչ է իրեն սպասում և հաղթականորեն հանեց դրոշակը։ Բայց արքայազն Անդրեյը չտեսավ, թե ինչպես դա ավարտվեց: Նրան թվաց, որ մոտակայքում գտնվող զինվորներից մեկը, ասես ամուր փայտը օրորելով, հարվածել է գլխին։ Դա մի փոքր ցավում էր, և որ ամենակարեւորն է, տհաճ էր, քանի որ այս ցավը նրան զվարճացնում էր և թույլ չէր տալիս տեսնել այն, ինչին նա նայում էր։
"Ինչ է սա? Ես ընկնում եմ? Ոտքերս տեղի են տալիս»,- մտածեց նա ու ընկավ մեջքի վրա։ Նա բացեց աչքերը՝ հույս ունենալով տեսնել, թե ինչպես է ավարտվել ֆրանսիացիների և հրետանավորների կռիվը, և ցանկանալով իմանալ՝ կարմիր մազերով հրետանավորը սպանվե՞լ է, թե՞ ոչ, զենքերը վերցվել են, թե՞ փրկվել։ Բայց նա ոչինչ չտեսավ։ Նրա վերևում այլևս ոչինչ չկար, բացի երկնքից, բարձր երկինք, ոչ պարզ, բայց դեռ անչափ բարձր, մոխրագույն ամպերով, որոնք հանգիստ սողում էին նրա վրայով: «Որքա՜ն լուռ, հանգիստ և հանդիսավոր, ամենևին նման չէ, թե ինչպես ես վազեցի», - մտածեց արքայազն Անդրեյը, - «ոչ այնպես, ինչպես մենք վազեցինք, գոռացինք և կռվեցինք. Դա ամենևին նման չէ, թե ինչպես ֆրանսիացին և հրետանավորը դառնացած և վախեցած դեմքերով քաշեցին միմյանց պաստառները. Ինչպե՞ս է, որ ես նախկինում չեմ տեսել այս բարձր երկինքը: Եվ որքան ուրախ եմ, որ վերջապես ճանաչեցի նրան։ Այո՛։ ամեն ինչ դատարկ է, ամեն ինչ խաբեություն է, բացի այս անծայրածիր երկնքից։ Չկա ոչինչ, ոչինչ, բացի նրանից։ Բայց նույնիսկ դա չկա, ոչինչ չկա, բացի լռությունից, հանգստությունից։ Եվ փառք Աստծուն…»:

Բագրատիոնի աջ թևում ժամը 9-ին գործը դեռ չէր սկսվել։ Չցանկանալով համաձայնվել Դոլգորուկովի պահանջին ՝ սկսելու բիզնեսը և ցանկանալով շեղել պատասխանատվությունը իրենից, արքայազն Բագրատիոնն առաջարկեց Դոլգորուկովին ուղարկել՝ այդ մասին հարցնելու գլխավոր հրամանատարին: Բագրատիոնը գիտեր, որ մի թեւը մյուսից բաժանող գրեթե 10 վերստ հեռավորության պատճառով, եթե ուղարկվածը չսպանվեր (ինչը շատ հավանական էր), և նույնիսկ եթե գտներ գլխավոր հրամանատարին, ինչը շատ դժվար էր, ուղարկվածը չէր հասցնի վերադառնալ ավելի վաղ երեկոյան։
Բագրատիոնը իր մեծ, անարտահայտիչ, քնից զրկված աչքերով շուրջը նայեց իր շքախմբին, և Ռոստովի մանկական դեմքը, ակամա սառած հուզմունքից և հույսից, առաջինը գրավեց նրա աչքը: Նա ուղարկեց այն:
- Իսկ եթե ես հանդիպեմ նորին մեծությանը գերագույն գլխավոր հրամանատարի առջև, Ձերդ գերազանցություն։ - ասաց Ռոստովը, ձեռքը բռնելով երեսկալին:
«Դուք կարող եք այն հանձնել ձերդ մեծությանը», - ասաց Դոլգորուկովը, շտապ ընդհատելով Բագրատիոնը:
Ազատվելով շղթայից՝ Ռոստովը հասցրեց առավոտից մի քանի ժամ քնել և իրեն զվարթ, համարձակ, վճռական զգաց, շարժումների այդ առաձգականությամբ, վստահությամբ իր երջանկության մեջ և այն տրամադրությամբ, որում ամեն ինչ հեշտ, զվարճալի և հնարավոր է թվում:
Այդ առավոտ կատարվեցին նրա բոլոր ցանկությունները. ընդհանուր ճակատամարտ է տեղի ունեցել, նա մասնակցել է դրան; Ավելին, նա կարգուկանոն էր ամենաքաջ գեներալի օրոք. Ավելին, նա ուղևորվում էր Կուտուզով, և գուցե նույնիսկ ինքնիշխանի մոտ։ Առավոտը պարզ էր, տակի ձին լավն էր։ Նրա հոգին ուրախ ու երջանիկ էր։ Ստանալով հրամանը, նա ճամփա ընկավ ձին և վազեց գծի երկայնքով։ Սկզբում նա հեծավ Բագրատիոնի զորքերի գծով, որը դեռ գործի չէր անցել և կանգնած էր անշարժ. այնուհետև նա մտավ Ուվարովի հեծելազորի զբաղեցրած տարածք և այստեղ արդեն նկատեց գործի նախապատրաստման շարժումներ և նշաններ. Անցնելով Ուվարովի հեծելազորի մոտ՝ նա արդեն հստակ լսում էր իր առջեւից թնդանոթի եւ կրակոցների ձայները։ Կրակոցներն ակտիվացել են.
Առավոտյան մաքուր օդում այլևս, ինչպես նախկինում, անկանոն ընդմիջումներով երկու, երեք կրակոց, ապա մեկ-երկու կրակոց չէր լսվում, իսկ լեռների լանջերին, Պրատցենի դիմաց, լսվում էին կրակոցների ձայներ, որոնք ընդհատվում էին։ հրացանների այնպիսի հաճախակի կրակոցներով, որ երբեմն թնդանոթի մի քանի կրակոցներ այլեւս չէին բաժանվում միմյանցից, այլ միաձուլվում էին մեկ ընդհանուր մռնչյունի մեջ:
Տեսանելի էր, թե ինչպես էր հրացանների ծուխը կարծես թե հոսում լանջերի երկայնքով՝ հասնելով միմյանց, և ինչպես էր հրացանների ծուխը պտտվում, մշուշվում և ձուլվում միմյանց հետ։ Ծխի արանքում սվինների փայլից տեսանելի էին հետևակի շարժվող զանգվածներն ու կանաչ արկղերով հրետանու նեղ շերտերը։
Ռոստովը մեկ րոպեով կանգնեցրեց իր ձին բլրի վրա՝ ուսումնասիրելու, թե ինչ է կատարվում. բայց որքան էլ նա լարեց իր ուշադրությունը, նա ոչ մի բան չէր կարողանում հասկանալ, ոչ էլ պարզել, թե ինչ է կատարվում. ոմանք ծխի մեջ շարժվում էին այնտեղ, զորքերի որոշ կտավներ շարժվում էին թե՛ առջևից, թե՛ հետևից. բայց ինչու? ԱՀԿ? Որտեղ? անհնար էր հասկանալ. Այս տեսարանն ու այս հնչյունները ոչ միայն նրա մեջ ոչ մի ձանձրալի կամ երկչոտ զգացում չառաջացրին, այլ ընդհակառակը, եռանդ ու վճռականություն տվեցին։
«Դե, ավելին, ավելին տվեք»: - Նա մտովի շրջվեց դեպի այս հնչյունները և նորից սկսեց սլանալ գծի երկայնքով՝ ավելի ու ավելի ներթափանցելով արդեն գործողության մեջ գտնվող զորքերի տարածք։
«Ես չգիտեմ, թե ինչպես կլինի այնտեղ, բայց ամեն ինչ լավ կլինի»: մտածեց Ռոստովը։
Անցնելով ավստրիական որոշ զորքեր՝ Ռոստովը նկատեց, որ գծի հաջորդ հատվածը (դա պահակն էր) արդեն գործի է անցել։
«Ամեն լավ! Ես ավելի մոտիկից կնայեմ », - մտածեց նա:
Նա քշեց գրեթե առաջին գծով։ Մի քանի ձիավորներ սլացան դեպի նրա կողմը։ Սրանք մեր կյանքի նիզակներն էին, ովքեր անկարգ շարքերով վերադառնում էին հարձակումից։ Ռոստովը նրանց կողքով անցավ, ակամայից նկատեց նրանցից մեկին արնաշաղախ ու սլացավ։
«Ինձ դա չի հետաքրքրում»: նա մտածեց. Մինչ նա սրանից մի քանի հարյուր քայլ հեծած, ձախ կողմում, դաշտի ողջ երկայնքով, հայտնվեց մի հսկայական զանգված՝ սև ձիերի վրա նստած, սպիտակ փայլուն համազգեստով հեծելազորների՝ ուղիղ դեպի նրա կողմը սլացող։ Ռոստովն իր ձիուն դրեց ամբողջ վազքով, որպեսզի դուրս գա այս հեծելազորների ճանապարհից, և նա կհեռանար նրանցից, եթե նրանք պահպանեին նույն քայլքը, բայց նրանք շարունակում էին արագացնել, այնպես որ որոշ ձիեր արդեն վազում էին։ Ռոստովը ավելի ու ավելի պարզ էր լսում նրանց թրթռոցն ու զենքերի զրնգոցը, և նրանց ձիերը, կերպարանքները և նույնիսկ դեմքերը ավելի տեսանելի էին դառնում։ Սրանք մեր հեծելազորային պահակախումբն էին, որոնք հարձակման էին ենթարկվում ֆրանսիական հեծելազորի վրա, որը շարժվում էր դեպի նրանց։
Հեծելազորի պահակները սլացան, բայց դեռ ձիերը բռնած։ Ռոստովն արդեն տեսել է նրանց դեմքերը և լսել հրամանը՝ «երթ, երթ»: արտասանված սպայի կողմից, ով ամբողջ արագությամբ արձակեց իր արյունոտ ձին: Ռոստովը, վախենալով ջախջախվելուց կամ գայթակղվել ֆրանսիացիների վրա հարձակման մեջ, սլացավ ճակատի երկայնքով այնքան արագ, որքան կարող էր իր ձին, և դեռ չկարողացավ անցնել նրանց կողքով:
Հեծելազորի վերջին պահակը, մի վիթխարի, ծակոտկեն մարդ, զայրացած դեմքը խոժոռվեց, երբ իր դիմաց տեսավ Ռոստովին, որի հետ անխուսափելիորեն կբախվեր։ Այս հեծելազորի պահակը, անշուշտ, տապալած կլիներ Ռոստովին և նրա բեդվինին (այդ հսկա մարդկանց ու ձիերի համեմատությամբ Ռոստովն ինքը այնքան փոքր ու թույլ էր թվում), եթե մտրակը չխոթեր հեծելազորի պահակի ձիու աչքերի մեջ։ Սև, ծանր, հինգ մատնաչափ ձին փախավ, ականջները ցած դնելով. բայց ձիավոր հեծելազորի պահակն ահռելի նժույգներ խփեց նրա կողերին, և ձին, պոչը թափահարելով և վիզը ձգելով, ավելի արագ շտապեց։ Հենց որ հեծելազորը անցավ Ռոստովը, նա լսեց, թե ինչպես են նրանք գոռում. և հետ նայելով նա տեսավ, որ նրանց առաջին շարքերը խառնվում էին անծանոթների, հավանաբար ֆրանսիացիների, կարմիր էպուլետներով հեծյալների հետ։ Ավելի հեռուն անհնար էր որևէ բան տեսնել, քանի որ դրանից անմիջապես հետո ինչ-որ տեղից սկսեցին կրակել թնդանոթները, և ամեն ինչ ծածկվեց ծխով։
Այդ պահին, երբ հեծելազորի պահակները, անցնելով նրա կողքով, անհետացան ծխի մեջ, Ռոստովը տատանվեց՝ ցատկե՞լ նրանց հետևից, թե՞ գնալ այնտեղ, ուր պետք է գնալ։ Սա հեծելազորի պահակախմբի այդ փայլուն հարձակումն էր, որը զարմացրեց հենց ֆրանսիացիներին։ Ռոստովը վախեցավ՝ հետո լսելով, որ հսկա գեղեցիկ մարդկանց այս ամբողջ զանգվածից, այս բոլոր հանճարեղ, հարուստ երիտասարդներից, սպաներից և կուրսանտներից, որոնք հազարավոր ձիեր հեծած, վազելով անցնում էին իր կողքով, հարձակումից հետո մնաց ընդամենը տասնութ մարդ: