Ինչ է կապված գրաֆիկը բացատրել օրինակով:

2024 Հեղինակ: Miles Stephen | [email protected]. Վերջին փոփոխված: 2023-12-15 23:37

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

Նաև գիտեք, թե ինչ է կապված գրաֆիկը:

Միացված գրաֆիկ . Ա գրաֆիկ որն է միացված տեղաբանական տարածության իմաստով, այսինքն՝ կա ուղի ցանկացած կետից դեպի ցանկացած այլ կետ գրաֆիկ . Ա գրաֆիկ դա չէ միացված ասվում է, որ անջատված է:

Նմանապես, ի՞նչ է 2 կապակցված գրաֆիկը: Ա գրաֆիկ է միացված եթե որևէ մեկի համար երկու գագաթներ x, y ∈ V (G), կա մի ճանապարհ, որի վերջնակետերն են xand y: Ա միացված գրաֆիկ G կոչվում է 2 - միացված , եթե յուրաքանչյուր x ∈ V (G) գագաթի համար G− x է միացված . 2 − կապակցված գրաֆիկ.

Նաև հարց է, թե ինչ է միացված ցանցը:

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

Ինչպե՞ս որոշել, արդյոք գրաֆիկը միացված է կամ անջատված:

G կոչվում է անջատված , եթե այն ունի մեկից ավելի բաղադրիչ, այսինքն. եթե դա չէ միացված . Անեդջը ա միացված գրաֆիկ կամուրջ է, եթե դրա հեռացումը թողնում ա անջատված գրաֆիկ . A-ի գագաթը կապակցված գրաֆիկ կտրվածքի կամ հոդակապման կետ է, եթե դրա հեռացումը թողնում ա անջատված գրաֆիկ.