Գրաֆիկի տեսություն. Գրաֆների տեսությունը դիսկրետ մաթեմատիկայի ընդարձակ անկախ ճյուղ է

Կորոբովա Անաստասիա, ուսանող գր. 14-PGS-48D

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

«Գրաֆիկ» բառը մաթեմատիկայում նշանակում է նկար, որտեղ գծված են մի քանի կետեր, որոնցից մի քանիսը միացված են գծերով։ Նախ, հարկ է ասել, որ հաշվարկները, որոնք կքննարկվեն, ոչ մի կապ չունեն անցյալի արիստոկրատների հետ։ Մեր «գրաֆիկները» առաջացել են հունարեն «grapho» բառից, որը նշանակում է «գրում եմ»։ Նույն արմատը «գրաֆիկ», «կենսագրություն» բառերում։

Գրաֆների տեսության վերաբերյալ առաջին աշխատանքը պատկանում է Լեոնհարդ Էյլերին, և այն հայտնվել է 1736 թվականին Սանկտ Պետերբուրգի Գիտությունների ակադեմիայի հրատարակություններում։

Հաշվարկները համապատասխանում են.

ֆիզիկայում՝ էլեկտրական շղթաների կառուցման մեջ

քիմիայի և կենսաբանության մեջ՝ դրանց շղթաների մոլեկուլների ուսումնասիրության մեջ

պատմության մեջ - տոհմածառեր կազմելիս (տոհմային)

աշխարհագրության մեջ՝ քարտեզագրման մեջ

երկրաչափության մեջ՝ բազմանկյունների, բազմանկյունների, տարածական պատկերների գծագրեր

տնտեսագիտության մեջ - բեռնափոխադրումների հոսքերի օպտիմալ ուղու ընտրության խնդիրներ լուծելիս (ավիաընկերություններ, մետրո, երկաթուղիներ)

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

Այժմ գիտության և տեխնիկայի ցանկացած ճյուղում դուք հանդիպում եք գրաֆիկներով:

Բեռնել:

Նախադիտում:

Ներկայացումների նախադիտումն օգտագործելու համար ստեղծեք Google հաշիվ (հաշիվ) և մուտք գործեք՝ https://accounts.google.com

Սլայդների ենթագրեր.

Ներկայացում մաթեմատիկայում Թեմա՝ «Գծանկարներ» Ավարտել է 14-PGS-48D խմբի աշակերտուհի Կորոբովա Անաստասիա

Գրաֆիկը պատկեր է, որը բաղկացած է այս կետերը միացնող կետերից և գծերից: Գծերը կոչվում են գրաֆիկի եզրեր, իսկ կետերը՝ գագաթներ։ Այն գագաթները, որոնցից դուրս են գալիս զույգ թվով եզրեր, կոչվում են զույգ, կենտ թիվը՝ կենտ: Գրաֆիկների գրաֆիկների տեսության օրինակներ

Լեոնհարդ Էյլերը (ապրիլի 4, 1707, Բազել, Շվեյցարիա - սեպտեմբերի 7, 1783, Սանկտ Պետերբուրգ, Ռուսական կայսրություն), շվեյցարացի, գերմանացի և ռուս մաթեմատիկոս, ով նշանակալից ներդրում է ունեցել մաթեմատիկայի, ինչպես նաև մեխանիկայի, ֆիզիկայի զարգացման մեջ։ աստղագիտություն և մի շարք կիրառական գիտություններ։ Էյլերը ավելի քան 800 աշխատությունների հեղինակ է մաթեմատիկական վերլուծության, դիֆերենցիալ երկրաչափության, թվերի տեսության, մոտավոր հաշվարկների, երկնային մեխանիկայի, մաթեմատիկական ֆիզիկայի, օպտիկայի, բալիստիկայի, նավաշինության, երաժշտության տեսության և այլնի վերաբերյալ։

Նկարը (գրաֆիկը), որը կարելի է նկարել՝ առանց մատիտը թղթից բարձրացնելու, կոչվում է unicursal: Նախշ 1. Գրաֆիկը, որն ունի ընդամենը երկու կենտ գագաթ, կարելի է նկարել առանց մատիտը թղթից բարձրացնելու, և շարժումը պետք է սկսվի այս կենտ գագաթներից մեկից և ավարտվի դրանցից երկրորդում: (նկ. Ա) Կաղապար 2: Երկու կենտ գագաթներով գրաֆիկը չի կարող գծվել «մեկ հարվածով» (նկ. Բ) Էյլերի գրաֆիկներ B A

Կանոնավորություն 3. Եթե գրաֆիկի բոլոր գագաթները հավասար են, ապա առանց մատիտը թղթից հանելու, յուրաքանչյուր եզրով միայն մեկ անգամ գծելով, գծե՛ք այս գրաֆիկը: Շարժումը կարող է սկսվել ցանկացած գագաթից և ավարտվել նույն գագաթով:

Երկար ժամանակ Քյոնիգսբերգի բնակիչների շրջանում տարածված է այսպիսի հանելուկ՝ ինչպե՞ս անցնել բոլոր կամուրջներով (Պրեգոլիա գետով)՝ երկու անգամ չանցնելով դրանցից որևէ մեկի միջով։ Շատերը փորձեցին լուծել այս խնդիրը թե՛ տեսականորեն, թե՛ գործնականում զբոսանքների ժամանակ Քյոնիգսբերգի կամուրջների խնդիրը։

Սա գրաֆիկ է, որում որոշ եզրեր կարող են ուղղորդված լինել, իսկ որոշները՝ չուղղորդված: Խառը հաշվարկ

Կշռված գրաֆիկ 1 2 4 2 3 A B C D E

Ծառը ցանկացած կապակցված գրաֆիկ է, որը չունի ցիկլեր: Ծառեր Ծառեր

Սա (բազմաթիվ) գրաֆիկ է, որի եզրերին տրված է ուղղություն: Ուղղորդված եզրերը կոչվում են նաև աղեղներ: Ուղղորդված գրաֆիկ

Հաշվարկները համապատասխանում են.

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

Շնորհակալություն ուշադրության համար:

ուսանողներին ծանոթացնել «Գրաֆիկ» հասկացությանը, դրա կառուցման հիմնական սկզբունքներին.

ձևավորել առարկաները կապող հարաբերություններ ընդգծելու ունակություն.

զարգացնել ուշադրությունը, տրամաբանական դատողությունների կարողությունը.

խթանել փոխօգնությունը, թիմում աշխատելու կարողությունը

ձեռք բերված գիտելիքների համախմբում գործնականում

հիշողության, ուշադրության զարգացում;

անկախության զարգացում;

ճանաչողական գործունեության կրթություն.

Սարքավորումներ:

• ժամանակակից տեխնիկայով հագեցած համակարգչային դասարան, վիդեո պրոյեկտոր, էկրան;
• համակարգիչներ Windows XP OS-ով, ծրագիր Microsoft Office PowerPoint 2003;
• գրատախտակի սարքավորումներ (դասի թեմա, նոր տերմիններ). Ձեռնարկ.

Դասի պլան.

II. Նոր նյութի ներկայացում. (10 րոպե)

III. Նյութի ամրագրում. Գործնական աշխատանք. (15-20 րոպե)

IV. Դասի ամփոփում (2ր.)

v. Տնային աշխատանք.

I. Կազմակերպչական պահ. Գիտելիքների թարմացում:

Բարեւ! Մեր դասը կոչվում է «Գծանկարներ»: Մենք կծանոթանանք «Գծանկարներ» հասկացությանը, կսովորենք, թե ինչպես դրանք պատկերել և լուծել այս թեմայի վերաբերյալ խնդիրներ:

II Նոր նյութի ներկայացում.

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

Գրաֆիկների օգնությամբ հաճախ պարզեցվում էր գիտելիքի տարբեր ոլորտներում ձևակերպված խնդիրների լուծումը՝ ավտոմատացում, էլեկտրոնիկա, ֆիզիկա, քիմիա և այլն։ . Գրաֆիկները օգնում են լուծել մաթեմատիկական և տնտեսական խնդիրները:

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

Գրաֆիկը որոշ տեղեկատվական մոդել է

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

Գրաֆիկների օրինակներ (Սլայդ 4, 5, 6)

Առաջադրանք 1 (Սլայդ 7):

Արեգակնային համակարգի ինը մոլորակների միջև տիեզերական հաղորդակցություն է հաստատվել։ Կանոնավոր հրթիռները թռչում են հետևյալ երթուղիներով.

Երկիր - Մերկուրի; Պլուտոն - Վեներա; Երկիր - Պլուտոն; Պլուտոն - Մերկուրի; Մերկուրի - Վեներա; Ուրան - Նեպտուն; Նեպտուն - Սատուրն; Սատուրն - Յուպիտեր; Յուպիտեր - Մարս; Մարս - Ուրան.

Հնարավո՞ր է սովորական հրթիռներով թռչել Երկրից Մարս:

Լուծում՝ գծենք պայմանի դիագրամ՝ մոլորակները կպատկերենք կետերով, իսկ հրթիռների երթուղիները՝ գծերով։

Այժմ անմիջապես պարզ է դառնում, որ անհնար է Երկրից Մարս թռչել։

Երկու գագաթները, որոնք կապված են աղեղով կամ եզրով, կոչվում են հարակից: Յուրաքանչյուր եզր կամ աղեղ կապված է թվի հետ: Թիվը կարող է ցույց տալ բնակավայրերի միջև եղած հեռավորությունը, մի գագաթից մյուսին անցնելու ժամանակը և այլն:

Առաջադրանք 2 (սլայդ 9) - լուծումը գրատախտակի մոտ է: Մաշան եկել է կենդանաբանական այգի և ցանկանում է որքան հնարավոր է շատ կենդանիներ տեսնել: Ո՞ր ճանապարհով նա պետք է գնա: Դեղին, կարմիր, կանաչ?

Առաջադրանք 3 (11 սլայդ) - լուծումը գրատախտակի մոտ է: Հինգ ֆուտբոլային թիմեր A, B, C, D, E պետք է միմյանց հետ հանդիպումներ անցկացնեն: Արդեն խաղացել է A-ն B, C, D-ի հետ; B c A, C, D. Քանի՞ հանդիպում է անցկացվել մինչ այժմ: Որքա՞ն է մնացել խաղալու:

Գրաֆիկի ներկայացում (Սլայդ 12)

Գրաֆիկը կարող է ներկայացվել որպես կամարների ցանկ (AB; 7), գրաֆիկական կամ աղյուսակի միջոցով:

Arc Ցուցակներ	Գրաֆիկական ձև	աղյուսակային ձև
(AB; 7),		ԲԱՅՑ IN ԻՑ ԲԱՅՑ 3 IN 4 ԻՑ 3 4

III. Նյութերի համախմբում. ուսանողներին առաջարկվում է բաժանվել խմբերի և կատարել առաջադրանքներ: Աշխատելով փոքր խմբում` ուսանողները դասի սկզբում ձեռք բերած տեսական գիտելիքների հիման վրա քննարկում են մոդելներ: Այսպիսով, ձեռք է բերվում նյութի կրկնություն և համախմբում:

Առաջադրանք 2 (Սլայդ 13)

IV. Դասի ամփոփում

Տղաներ, ի՞նչ նոր բառեր սովորեցիք այսօր: (Հաշիվ, գրաֆիկի գագաթ, գրաֆիկի եզրեր):

Ի՞նչ կարող են ներկայացնել գրաֆիկի գագաթները: (Քաղաքներ, օբյեկտներ, որոնք կապված են):

Ի՞նչ են նշանակում գրաֆիկի եզրերը (ուղիներ, շարժումներ, ուղղություններ)

Օրինակ բերեք, թե կյանքում որտեղ կարող ենք հանդիպել նրանց:

Ինչպե՞ս են ցուցադրվում գրաֆիկները:

V. Տնային աշխատանք. (Սլայդ 15)

Գագաթների թիվը կոչվում է
գրաֆիկի կարգը.
Ծայրերի թիվը կոչվում է
գրաֆիկի չափը.

Որոշ տերմիններ-1

- Թող R=(a,b) լինի գրաֆիկի եզրերից մեկը: Հետո
a և b գագաթները կոչվում են տերմինալ
եզրային գագաթներ;
- Նույն եզրի վերջավոր գագաթները
կոչվում է հարեւան;
- Երկու եզրեր կոչվում են կից, եթե ունեն
ընդհանուր վերջի գագաթ;
- Երկու եզրերը կոչվում են բազմակի, եթե
դրանց վերջի գագաթների բազմությունները համընկնում են.
- Եզրը կոչվում է հանգույց, եթե այն ավարտվում է
համընկնում.

Որոշ տերմիններ-2

- V գագաթի աստիճանը նշվում է deg(V)-ով:
կոչվում է եզրերի թիվ, համար
որի վերջն է այս գագաթը.
- Գագաթը կոչվում է մեկուսացված, եթե
նա ոչ մեկի համար վերջը չէ
կողիկներ;
- Գագաթը կոչվում է տերեւ, եթե այն
տերմինալ է հենց մեկի համար
կողիկներ. q թերթիկի համար ակնհայտ է, որ deg(q)=1:

Օրինակ:

deg(C)=4
H1,…H4 - Տերեւներ

Մեկ այլ օրինակ.

B և D քաղաքները մեկուսացված են
գագաթներ; G և E քաղաքները տերևներ են:

Ամբողջական գրաֆիկ

Գրաֆիկը կոչվում է ամբողջական, եթե այդպիսիք կան
երկու գագաթները միացված են եզրով:
Քանի՞ եզր ունի ամբողջական գրաֆիկը
պատվիրել n?
n կարգի ամբողջական գրաֆիկն ունի եզրերի քանակը
հավասար է Cn2=n!/(2*(n-2)!)=n*(n-1)/2

Եկեք ապացուցենք դա...

Լրացրեք գրաֆիկը երկու գագաթներով
պարունակում է մեկ եզր, սա ակնհայտ է:
Փոխարինեք n=2 n*(n-1)/2 բանաձևով
Մենք ստանում ենք.
n*(n-1)/2=1
Բանաձևը ճիշտ է n=2-ի համար

Ինդուկցիայի ենթադրություն

Ենթադրենք, որ բանաձևը ճիշտ է
գծապատկեր k գագաթներով.
Եկեք ապացուցենք, որ սա ենթադրում է
գրաֆիկի բանաձևի վավերականությունը
(k+1) գագաթով։

Կ գագաթներով ամբողջական գրաֆիկին ավելացնենք ևս մեկ գագաթ։

Եվ կապեք այն առաջին Կ
գագաթներ...

Մենք ստանում ենք.

Մենք հաշվում ենք, թե քանի կող ենք ստացել...

Կ*(Կ-1)/2 + Կ
=
K*(K+1)/2
Ստացվում է վերջին արտահայտությունը.
եթե n*(n-1)/2 բանաձեւում n-ի փոխարեն
փոխարինող K+1.

Արդարության ենթադրությունից
Հետևում է n=k-ի հայտարարությունը
հայտարարության վավերականությունը ժամը
n=k+1.
Թեորեմն ապացուցված է.

Ամբողջական գրաֆիկների օրինակներ

Կարևոր պարզաբանում

Չուղղորդված գրաֆիկում եզրերը սահմանող զույգերը դասավորված չեն (այսինքն.
զույգերը (ա, բ) և (բ, ա) չեն տարբերվում)

Ուղղորդված գրաֆիկ

Եթե ​​գրաֆիկի եզրերը բազմություն են
պատվիրված զույգեր (այսինքն (a,b) ≠ (b,a)),
Ասում են, որ գրաֆիկը ուղղված է:
(կամ դիագրաֆ)
Ինչպես կողմնորոշում տալ հայեցակարգին
տեսողական իմաստ.
Շատ պարզ - կողոսկրերը մատակարարված են
սլաքներ (սկզբից մինչև վերջ):

Դիգրաֆի օրինակ

Խառը հաշվարկ

Խառը գրաֆիկը եռակի է (V, E, A):
V-ը գագաթների բազմությունն է;
E-ն չուղղորդվածների բազմությունն է
կողիկներ;
A-ն ուղղորդված եզրերի ամբողջությունն է:
Ի դեպ, ուղղորդված եզրեր
կոչվում են աղեղներ:

Գրաֆիկի իզոմորֆիզմ

Թող լինի երկու գրաֆիկ G1 և G2
Եթե ​​կա մեկ առ մեկ նամակագրություն Ֆ
G1 և G2 գրաֆիկների գագաթների միջև, այնպիսին, որ.
- եթե G1 գրաֆիկում կա եզր (a,b), ապա G2 գրաֆիկում
կա եզր (F(a), F(b))
- եթե G2 գրաֆիկում կա եզր (p,q), ապա G1 գրաֆիկում
կա եզր (F-1(p),F-1(q))
ապա G1 և G2 գրաֆիկները կոչվում են իզոմորֆ, և
F համապատասխանությունը իզոմորֆիզմ է։

Պարզաբանում

Դիգրաֆների և խառը գրաֆիկների համար
F նամակագրությունը պետք է պահպանվի
աղեղային կողմնորոշում.

Իզոմորֆիզմի համար անհրաժեշտ պայման

Ինչ պայմաններում տարրերի միջև
երկու վերջավոր հավաքածու
սահմանել մեկ առ մեկ
համապատասխանություն?
Հետո և միայն այն ժամանակ, թիվը
տարրերը նույնն են.
Իզոմորֆիզմի համար անհրաժեշտ պայման
գրաֆիկները նույն թիվն են
գագաթները.

Այս պայմանը բավարա՞ր է։

Ոչ, քանի որ գագաթները կարող են լինել
կապված տարբեր ձևերով.

Արդյո՞ք այս գրաֆիկները իզոմորֆ են:

Գագաթների թիվը նույնն է.
առկա է անհրաժեշտ պայման...

Մենք փորձում ենք ստեղծել նամակագրություն F…

Սա իզոմորֆիզմ չէ. G1-ն ունի եզր (A, D),
իսկ G2-ում այս եզրերի պատկերները միացված չեն։

Եվս մեկ փորձ...

Եվ սա իզոմորֆիզմ է։

Արդյո՞ք այս գրաֆիկները իզոմորֆ են:

Ցավոք, ոչ…

Տեսական տեսանկյունից երկու
Իզոմորֆ գրաֆիկը նույնն է
նույն առարկան (միայն, գուցե, տարբեր կերպ պատկերված ...)

Ուղեր (շղթաներ).

Ճանապարհը (շղթան) հաջորդականություն է
գագաթներ:
a1, a2, …, an
որտեղ հարեւան գագաթները ai և ai+1
միացված է կողերով:
Ճանապարհի երկարությունը նրա բաղադրիչների քանակն է
կողիկներ

Ուղու օրինակներ.

(A, D, C) և (A, B, D) ուղիներ են: (A, B, C) ճանապարհը չէ:

Պահպանվում է երկգրաֆի համար ճանապարհ հասկացությունը
ուժ, բայց պետք է լրացվի.
հարևան գագաթները
հաջորդականություններ
a1, a2, …, an
պետք է միացված լինեն աղեղներով:

Ցիկլեր

Ցիկլը ուղի է, որի սկզբնական և
վերջ գագաթային համընկնում.
Ցիկլի երկարությունը նրա բաղադրիչների քանակն է
կողիկներ.
Ցիկլը կոչվում է պարզ, եթե դրա եզրերը
չեն կրկնվում։
Ցիկլը կոչվում է տարրական, եթե այն
պարզ, և դրա գագաթները չեն կրկնվում:

Միացման բաղադրիչներ

Կամայական գրաֆիկի գագաթները կարող են լինել
բաժանված են այնպիսի դասերի, որ համար
նույն դասի ցանկացած երկու գագաթ v1
իսկ v2 կա v1-ից v2 ուղի
Այս դասերը կոչվում են բաղադրիչներ
միացում:
Եթե ​​գրաֆիկն ունի ուղիղ մեկ բաղադրիչ
կապ, այնուհետև կանչվում է գրաֆիկը
կապված է։

Գրաֆիկների մեքենայական ներկայացում:

Հարակից մատրիցա

- Թվարկում ենք գրաֆիկի գագաթները Գ
1-ից n հաջորդական ամբողջ թվեր;
- Կառուցեք քառակուսի աղյուսակ n×n և
լրացրեք այն զրոներով;
- Եթե կա միացնող եզր
i և ​​j գագաթները, այնուհետև (i,j) և (j,i) դիրքերում
տեղադրել միավորներ;
- Ստացված աղյուսակը կոչվում է
Գրաֆիկի հարևանության մատրիցա Գ.

Օրինակ

Հարակից մատրիցայի որոշ ակնհայտ հատկություններ

- Եթե գագաթը մեկուսացված է, ապա նրա շարքը և
սյունակը լիովին զրոյական կլինի;
- Միավորների քանակը անընդմեջ (սյունակ)
հավասար է համապատասխան աստիճանի
գագաթներ;
- Չուղղորդված գրաֆիկի համար՝ մատրիցը
հարևանությունը սիմետրիկ է
հիմնական անկյունագիծ;
- Օղակը համապատասխանում է վրա կանգնած միավորին
հիմնական անկյունագիծ.

Ընդհանրացում երկգրաֆի համար

Հարակից մատրիցա երկգրաֆի համար
կարող է կառուցվել նմանատիպ
ճանապարհ, բայց հաշվի առնել կարգը
գագաթներով, դուք կարող եք դա անել.
Եթե ​​աղեղը գալիս է j գագաթից և
մտնում է k գագաթը, այնուհետև (j,k) դիրքում
սահմանել հարևանության մատրիցները 1-ի և in
դիրքը (k, j) սահմանված -1.

Դեպքերի մատրիցա

- Թվարկում ենք գրաֆիկի գագաթները Գ
հաջորդական ամբողջ թվեր 1-ից մինչև
n;
- Կառուցեք ուղղանկյուն սեղան
n տող և m սյունակ (սյունակներ
համապատասխանում է գրաֆիկի եզրերին);
- Եթե j-րդ եզրն ունի տերմինալ
vertex k, ապա դիրքում
(k,j) սահմանված է մեկ: Ընդհանուր առմամբ
այլ դեպքերում այն ​​սահմանվում է զրոյի:

Անցման մատրիցա երկգրաֆի համար

- Եթե j-րդ աղեղգալիս է k գագաթից,
ապա դիրքը (k,j) սահմանվում է 1;
- Եթե j-րդ աղեղը մտնում է k գագաթը, ապա
դիրքում (k,j) դրել -1.
- Մնացած դեպքերում (k, j) դիրքում.
մնում է զրո:

Քանի որ մատրիցայի սյուները
դեպքերը նկարագրում են եզրերը, ապա
յուրաքանչյուր սյունակ չի կարող պարունակել
ավելի քան երկու ոչ զրոյական տարրեր

Միջադեպի մատրիցայի օրինակ

Կողերի ցուցակ

Գրաֆիկը ներկայացնելու ևս մեկ եղանակ
– երկչափ զանգված (զույգերի ցանկ):
Զույգերի թիվը հավասար է եզրերի թվին
(կամ կամարներ):

Եզրերի ցանկի օրինակ

Ներկայացման տարբեր մեթոդների համեմատություն

- Եզրերի ցանկը ամենակոմպակտն է, և
նվազագույն պատահականության մատրիցա
կոմպակտ;
- Հիվանդության մատրիցան հարմար է, երբ
ցիկլերի որոնում;
- Հարակից մատրիցան ավելի հեշտ է
մնացածն օգտագործվում են։

Գրաֆիկի անցում

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

Համաձայնագիր-1

Գրաֆիկի որոնում կատարելուց առաջ
n գագաթներով ստեղծեք զանգված Chk
n տարրերից և լրացրեք այն
զրոներ.
Եթե ​​Chk[i] = 0, ապա i-րդ ​​գագաթդեռ
չի դիտվել:

Համաձայնագիր-2

Եկեք ստանանք տվյալների կառուցվածքը
(պահեստ), որում մենք կանենք
անգիր գագաթները գործընթացում
շրջանցում. Պահպանման ինտերֆեյս
պետք է ապահովի երեք գործառույթ.
- Վերև բերեք;
- Էքստրակտ վերև;
- Ստուգեք՝ արդյոք պահեստը դատարկ է.

Համաձայնագիր-3

Երբ j գագաթը տեղադրված է
պահոց, այն նշվում է որպես
դիտված (այսինքն՝ տեղադրված
Chk[j]=1)

Շրջանցման ալգորիթմ-1

1) Մենք վերցնում ենք կամայական սկզբնական գագաթ,
տպեք այն և դրեք այն պահեստում;

3) Վերցրեք Z գագաթը պահեստից.
4) Եթե կա Z-ի հետ կապված Q գագաթ, և ոչ
ստուգված, այնուհետև մենք վերադարձնում ենք Z-ը պահեստ,
խանութ Q, տպել Q;
5) Անցեք 2-րդ քայլին

Շրջանցման ալգորիթմ-2

1) Վերցնում ենք կամայական սկզբնական գագաթ և
մենք այն դնում ենք պահեստում;
2) պահեստը դատարկ է: Եթե ​​ԱՅՈ - վերջ;
3) Վերցրեք Z գագաթը պահեստից, տպեք և
ջնջել պահեստից;
4) Մենք պահում ենք բոլոր գագաթները,
կապված Z-ի հետ և դեռ նշված չէ;
5) Անցեք 2-րդ քայլին

Տվյալների ո՞ր կառուցվածքներն են հարմար որպես պահեստ:

- Կույտ (PUSH - բերել; POP - հեռացնել)
- Հերթ (ENQUE - մուտքագրեք; DEQUE -
քաղվածք)
Երկու կառույցներն էլ թույլ են տալիս ստուգել
տվյալների առկայություն:

Ալգորիթմ-1 համակցված ստեկի հետ
կոչվում է խորության անցում
Ալգորիթմ-2՝ համակցված հերթի հետ
կոչվում է լայնության առաջին

Գրաֆիկը V գագաթների վերջավոր բազմություն է և R գագաթները միացնող զույգ գագաթներ, G=(V,R): V և R բազմությունների կարդինալությունները հավասար են N և M-ի: Եզրերի բազմությունը կարող է դատարկ լինել: Գագաթների օրինակներ են ցանկացած բնույթի օբյեկտներ (բնակավայրեր, համակարգչային ցանցեր): Ծայրերի օրինակներ են ճանապարհները, կողմերը, գծերը:

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

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

Միջադեպերի մատրիցա

Հաղորդակցության ցուցակներ

Կողերի ցուցակ

Գրաֆի միացված կշռված չուղղորդված գրաֆիկի հարակից մատրիցա

Նվազագույն քաշով միացված ծառի կառուցում: Կրուսկալի ալգորիթմ Բոլոր եզրերը հանվում են գրաֆիկից, և ստացվում է ընդգրկող ենթագրաֆ, որտեղ բոլոր գագաթները մեկուսացված են։ Յուրաքանչյուր գագաթ տեղադրված է մեկ տոնային ենթաբազմության մեջ: Ծայրերը դասավորված են կշիռների աճման կարգով։ Ծայրերը հաջորդաբար, իրենց կշիռների աճման կարգով, ներառված են ծածկված ծառի մեջ:

Կան 4 դեպք. 1) ներառված եզրի երկու գագաթները պատկանում են մեկ տարրի ենթաբազմություններին, այնուհետև դրանք միավորվում են նոր, միացված ենթաբազմության մեջ. 2) գագաթներից մեկը պատկանում է միացված ենթաբազմությանը, իսկ մյուսը` ոչ, ապա երկրորդը ներառում ենք ենթաբազմության մեջ, որին պատկանում է առաջինը. 3) երկու գագաթները պատկանում են տարբեր միացված ենթաբազմությունների, ապա միավորում ենք ենթաբազմությունները. 4) Երկու գագաթները պատկանում են նույն միացված ենթաբազմությանը, ապա մենք բացառում ենք այս եզրը:

Գրաֆիկի համար նվազագույն քաշով ընդգրկող ծառի կառուցման օրինակ GG Կատարված գործողություններ Գագաձևերի հավաքածու Գծապատկեր 1 Կառուցեք ընդգրկող ենթագրաֆ մեկուսացված և գագաթներով Մենք ստանում ենք 5 միանգամյա ենթաբազմություն՝ (V 1 ), (V 2 ), (V 3 ), ( V 4 ), (V 5 ) 2Գտե՛ք նվազագույն քաշի եզրը (R 15) և ավելացրե՛ք այն ընդգրկող ենթագրաֆում Ձևավորե՛ք գագաթների միացված ենթաբազմություն՝ (V 1,V 5 )։ Պահպանել ենթաբազմությունները (V 2 ), (V 3 ), (V 4 )

Կատարված գործողություններ Գագաձևերի բազմությունԳրաֆիկ 3 Մնացածներից գտե՛ք նվազագույն քաշի եզրը (R 45) և ավելացրե՛ք այն ընդգրկող ենթագրաֆում, իսկ գագաթը ավելացրեք միացված ենթաբազմությանը (V 1,V 5, V 4): Պահպանում ենք ենթաբազմությունները (V 2 ), (V 3 ) 4 Մնացածների մեջ գտնում ենք նվազագույն քաշի եզրը (R 23) և ավելացնում այն ​​ընդգրկող ենթագրաֆում Ձևավորելով գագաթների նոր միացված ենթաբազմություն. . Մենք պահում ենք առաջին միացված ենթաբազմությունը (V 1, V 5, V 4 ):

Կատարված գործողություններ Գագաձևերի հավաքածու Գծապատկեր 5 Մնացածներից գտեք նվազագույն քաշի եզրը (R 25) և ավելացրեք այն ընդգրկող ենթագրաֆում: Միավորեք ենթաբազմությունները մեկ միացված ենթաբազմության մեջ (V 1, V 5, V 4, V 2, V 3 ): 6 Մնացած եզրերը ներառված չեն գրաֆիկում, քանի որ նրանց բոլոր գագաթներն արդեն պատկանում են նույն միացված բազմությանը:

Կատարված գործողություններ Գագաձևերի բազմություն Ստացվել է գրաֆիկ 7A գրաֆիկը, որը. միացված (բոլոր գագաթները կարող են միացվել երթուղիներով); ծառ (առանց ցիկլերի); ունի նվազագույն քաշ. 8Արդյունքում ընկած ծառն ունի նվազագույն քաշ՝ R 12 +R 25 +R 15 +R 45 = =80 9 G գրաֆիկի ցիկլային թիվը γ=m-n+1=8-5+1=4 է, որը համապատասխանում է. եզրերի թիվը ոչ ծառի մեջ:

Փոփոխականների հայտարարում Երկու հինգ տարրից բաղկացած X և Y ամբողջ զանգված՝ գրաֆիկի գագաթի կոորդինատները պահելու համար Ամբողջ թվով երկչափ զանգված R գրաֆիկի եզրերի կշիռները պահելու համար. i, n և k ամբողջ փոփոխականները ցիկլի հաշվիչների համար Ամբողջական S ամբողջ փոփոխական՝ ծառերի ծայրերի կշիռների գումարը պահելու համար։ նվազագույն քաշով

Գրաֆի 5 գագաթների պատահական կոորդինատների առաջացում (շրջապտույտ i-ի վրա): Եզրերի կշիռների հաշվարկ: Կշռված երկգրաֆի հարևանության մատրիցայի դուրսբերում (n-ով և k-ով տեղադրված հանգույցներ) Կշռված չուղղորդված գրաֆիկի հարևանության մատրիցայի դուրսբերում – սկզբնական մատրիցայի տարրերի կեսը (սկզբնական արժեքը k=n+1) Ծրագրի մարմին.