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

չ
clean up, փոխարինվեց: → (2), ): → )։ (2) oգտվելով ԱՎԲ
չ (փոխարինվեց: 5թ → 5 թ oգտվելով ԱՎԲ)
չ (clean up, փոխարինվեց: → (2), ): → )։ (2) oգտվելով ԱՎԲ)
[[Պատկեր:Multi-pseudograph.svg|thumb|Սա չկողմնորոշված պսևդոգրաֆ է, քանի որ պարունակում է ինչպես պատիկ կողեր (կարմիր), այնպես էլ օղակներ (կապույտ)]]
 
'''Գրաֆը''' սահմանվում է որպես կարգավոր զույգ <math>G=(V,E)</math>, որտեղ V-ն '''գագաթների''' (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ '''կողերի''' (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ):։ Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են ''չկողմնորոշված'' և ''հասարակ'' գրաֆներ։
 
Կողին պատկանող գագաթները կոչվում են այդ գագաթի ''ծայրակետեր'': Հաճախ <math>\{u, v\}</math> կողը կրճատ նշանակում են <math>uv</math>-ով։
Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ։ Այս և այլ ոլորտներում ծագող բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային [[ալգորիթմ]]ներով։
 
Համակարգչային գիտություններում գրաֆներով մոդելավորում են համակարգչային ցանցերը, տվյալների կառուցվածքները, հաշվարկի ընթացքը և այլն։ Օրինակ, որպես գագաթների բազմություն կարելի է ընտրել ինտերնետային կայքերը, իսկ կայքերի միջև հղումները կդառնան ուղղորդված կողեր գագաթների միջև։ Գրաֆների միջոցով ներկայացվող տվյալները արդյունավետ պահելու և կառավարելու համար գոյություն ունեն գրաֆային [[տվյալների հենք]]եր։ Գրաֆների տեսությամբ են մոդելավորվում գերմեծ ինտեգրալ սխեմաների նախագծման ժամանակ առաջացող բազմաթիվ խնդիրներ (օրինակ՝ routing-ի խնդիրը):։
 
Քիմիայում և պինդ մարմնի ֆիզիկայում գրաֆների միջոցով մոդելավորում են ատոմները և նրանց միջև կապերը։
Ակնհայտորեն, միևնույն գրաֆը կարելի է պատկերել տարբեր ձևերով, և ընդհանուր դեպքում դժվար է ճանաչել, թե երբ են տարբեր պատկերները համապատասխանում միևնույն գրաֆին։ Գրաֆների գեղեցիկ կամ հարմար պատկերումը գրաֆների տեսության բարդագույն խնդիրներից է։ Մշակված են մի շարք որակի չափանիշներ (կողերի հատումների թիվը, համաչափությունը, գագաթների հեռավորությունը իրենցով չանցնող կողերից և այլն), ինչպես նաև բազմաթիվ պատկերման ալգորիթմներ <ref>[http://www.graphdrawing.org/ Գրաֆների պատկերում (անգլերեն)]</ref>:
 
Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են [[''հարթ'' գրաֆներ|հարթ գրաֆներ]]: Ընդհանուր դեպքում, կողերի հատումների նվազագույն քանակը, որին կարելի է հասնել գրաֆը հարթության վրա պատկերելիս, կոչվում է գրաֆի [[խաչումների թիվ]] <ref>[[Խաչումների թիվ|Խաչումների թվի]] մասին [http://mathworld.wolfram.com/GraphCrossingNumber.html Wolfram MathWorld-ում]</ref>: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի։ Հարթ գրաֆների հետազոտությունը, ինչպես տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են։ Գրաֆների պատկերման խնդիրները այլ մակերևույթների վրա (օրինակ՝ տոռերի) ուսումնասիրում է ''տոպոլոգիական գրաֆների տեսությունը'':
 
==Գրաֆների տեսության խնդիրներ==
Նման խնդիրներ դրվում են նաև [[ծնված ենթագրաֆ]]ների համար։ Այս խնդիրներն էլ հաճախ բարդ են։ Օրինակ, տրված գրաֆում մեծագույն [[անկախ բազմություն]] գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է։
 
Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը։ H գրաֆը կոչվում է G գրաֆի [[մինոր (գրաֆների տեսություն)|'''մինոր''']], եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր [[կծկելով]]: Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է։ [[Վագների թեորեմ]]ը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում <math>K_{3,3}</math> [[լրիվ երկկողմանի գրաֆ]]ը և <math>K_5</math> լրիվ գրաֆը որպես մինոր։
 
=== Գրաֆների ներկումներ ===
1 105 242

edits