«Գրաֆների տեսություն»–ի խմբագրումների տարբերություն

Content deleted Content added

Գծային

21:17, 6 Դեկտեմբերի 2014-ի տարբերակ

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

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

Գրաֆների տեսության հիմնական հասկացությունների համար այցելեք Գրաֆների տեսության բառարան։



Մեկից ութ գագաթանի լրիվ գրաֆները․ $K_{1}...K_{8}$ :

Սահմանումներ

Գրաֆը սահմանվում է որպես կարգավոր զույգ G=(V,E), որտեղ V-ն գագաթների (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ կողերի (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են չկողմնորոշված և հասարակ գրաֆներ:

Կողին պատկանող գագաթները կոչվում են այդ գագաթի ծայրակետեր: Հաճախ {u, v} կողը կրճատ նշանակում են uv-ով:

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

Սովորաբար V և E բազմությունները ընդունվում են վերջավոր: Հակառակ դեպքում գործ ունենք անվերջ գրաֆների հետ, որոնց համար վերջավոր գրաֆների բազմաթիվ հատկություններ տեղի չունեն: Գրաֆի կարգը գագաթների բազմության հզորությունն է: Որևէ գագաթի աստիճանը այդ գագաթին միացած կողերի քանակն է: Պսևդոգրաֆների դեպքում, երբ որևէ կողի երկու ծայրերն էլ միացած են միևնույն գագաթին, այդպիսի կողերը (օղակները) հաշվվում են երկու անգամ:

Կիրառություններ

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

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

Քիմիայում և պինդ մարմնի ֆիզիկայում գրաֆների միջոցով մոդելավորում են ատոմները և նրանց միջև կապերը:

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

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

Ակնհայտորեն, միևնույն գրաֆը կարելի է պատկերել տարբեր ձևերով, և ընդհանուր դեպքում դժվար է ճանաչել, թե երբ են տարբեր պատկերները համապատասխանում միևնույն գրաֆին: Գրաֆների գեղեցիկ կամ հարմար պատկերումը գրաֆների տեսության բարդագույն խնդիրներից է: Մշակված են մի շարք որակի չափանիշներ (կողերի հատումների թիվը, համաչափությունը, գագաթների հեռավորությունը իրենցով չանցնող կողերից և այլն), ինչպես նաև բազմաթիվ պատկերման ալգորիթմներ ^[1]:

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

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

Ենթագրաֆներ, մինորներ

Գրաֆների տեսության հետաքրքիր խնդիրներից է ենթագրաֆների իզոմորֆիզմի խնդիրը, երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի ենթագրաֆի գոյությունը: Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) ժառանգական են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը: Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է: Մասնավորապես, տրված գրաֆում ամենամեծ լրիվ գրաֆ ենթագրաֆի գտնելը NP-լրիվ խնդիր է^[2]:

Նման խնդիրներ դրվում են նաև ծնված ենթագրաֆների համար: Այս խնդիրներն էլ հաճախ բարդ են: Օրինակ, տրված գրաֆում մեծագույն անկախ բազմություն գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է:

Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը: H գրաֆը կոչվում է G գրաֆի մինոր, եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր կծկելով: Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է: Վագների թեորեմը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում K_3,3 լրիվ երկկողմանի գրաֆը և K₅ լրիվ գրաֆը որպես մինոր:

Վիքիպահեստ նախագծում կարող եք այս նյութի վերաբերյալ հավելյալ պատկերազարդում գտնել Գրաֆների տեսություն կատեգորիայում։

Կաղապար:Link FA

↑ Գրաֆների պատկերում (անգլերեն)
↑ Մեծագույն լրիվ ենթագրաֆի հզորությունը կոչվում է clique number: Ավելի մանրամասն՝ Wolfram MathWorld: Clique Number

[1] Գրաֆների պատկերում (անգլերեն)

[2] Մեծագույն լրիվ ենթագրաֆի հզորությունը կոչվում է clique number: Ավելի մանրամասն՝ Wolfram MathWorld: Clique Number

[1]

[2]

@@ Տող 43. / Տող 43. @@
 Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են  [[''հարթ'' գրաֆներ|հարթ գրաֆներ]]: Եթե այդպիսի պատկերում հնարավոր չէ, ապա հատումների նվազագույն քանակը, որին կարելի է հասնել, կոչվում է գրաֆի [[խաչումների թիվ]]: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի: Հարթ գրաֆների հետազոտությունը, ինչպես նաև տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են:
+==Գրաֆների տեսության խնդիրներ==
+===Ենթագրաֆներ, մինորներ===
+Գրաֆների տեսության հետաքրքիր խնդիրներից է '''ենթագրաֆների իզոմորֆիզմի խնդիրը''', երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի [[ենթագրաֆ]]ի գոյությունը: Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) '''ժառանգական''' են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը: Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է: Մասնավորապես, տրված գրաֆում ամենամեծ [[լրիվ|լրիվ գրաֆ]] ենթագրաֆի գտնելը [[NP-լրիվ խնդիր]] է<ref>Մեծագույն լրիվ ենթագրաֆի հզորությունը կոչվում է clique number: Ավելի մանրամասն՝ [http://mathworld.wolfram.com/CliqueNumber.html Wolfram MathWorld: Clique Number]</ref>:
+Նման խնդիրներ դրվում են նաև [[ծնված ենթագրաֆ]]ների համար: Այս խնդիրներն էլ հաճախ բարդ են: Օրինակ, տրված գրաֆում մեծագույն [[անկախ բազմություն]] գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է:
+Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը: H գրաֆը կոչվում է G գրաֆի [[մինոր (գրաֆների տեսություն)|մինոր]], եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր [[կծկելով]]:  Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է: [[Վագների թեորեմ]]ը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում ''K''<sub>3,3</sub> [[լրիվ երկկողմանի գրաֆ]]ը և ''K''<sub>5</sub> լրիվ գրաֆը որպես մինոր:
 {{ՎՊԵ|Graph theory}}