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

չ
Լավ/Ընտրյալ հոդվածի կամ ցանկի կաղապարների հեռացում: Այժմ Վիքիշտեմարանից է գալիս։, ջնջվեց: {{link FA|nl}}
չ (math mode)
չ (Լավ/Ընտրյալ հոդվածի կամ ցանկի կաղապարների հեռացում: Այժմ Վիքիշտեմարանից է գալիս։, ջնջվեց: {{link FA|nl}})
[[File:Complete graph K6.svg|thumb|Վեց գագաթանի [[լրիվ գրաֆ]] <math>K_6</math>]]
[[Մաթեմատիկա]]յում և [[Ինֆորմատիկա|համակարգչային գիտության]] մեջ '''գրաֆների տեսությունը''' ուսումնասիրում է [[գրաֆներ]]ը, որոնք օբյեկտների միջև զույգ առ զույգ կապերը մոդելավորող մաթեմատիկական օբյեկտներ են: Գրաֆը կազմված է ''գագաթներից'' (կամ ''հանգույցներից'') և ''կողերից'', որոնք միացնում են գագաթների որոշ զույգեր:
 
Գրաֆը կարող է լինել չուղղորդված (չկողմնորոշված), երբ յուրաքանչյուր կողի երկու ծայրակետերը համարժեք են, կամ կողերը կարող են ուղղորդված (կողմնորոշված) լինել մի ծայրակետից մյուսը: Գրաֆները [[դիսկրետ մաթեմատիկա]] բաժնում ուսումնասիրվող պարզագույն օբյեկտներից են։
 
==Կիրառություններ==
[[File:Wikipedia multilingual network graph July 2013.svg|thumb|Գագաթները [[Վիքիպեդիա]]յի լեզվական տարբերակներն են: Կողերով միացված են այն տարբերակները, որոնցում խմբագրումներ կատարել է միևնույն մասնակիցը 2013-ի ամռանը կատարված հետազոտության ժամանակ <ref>[http://arxiv.org/abs/1312.0976 Scott Hale, Multilinguals and Wikipedia Editing, 2013 [http://arxiv.org/abs/1312.0976]</ref>]]
 
Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ: Այս և այլ ոլորտներում ծագող բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային [[ալգորիթմ]]ներով:
==== Գագաթային ներկումներ ====
''Ճիշտ գագաթային ներկման'' դեպքում գագաթներին համապատասխանեցվում են գույներ (թվեր) այնպես, որ հարևան գագաթների գույները լինեն տարբեր: Ակնհայտորեն, բոլոր գրաֆները ունեն այդպիսի ներկումներ, քանի որ կարելի է ամեն գագաթին համապատասխանեցնել մի նոր գույն: Սակայն խնդիր է առաջանում գտնել գույների ամենափոքր թիվը, որոնցով կարելի է ապահովել ճիշտ գագաթային ներկում: Այդ թիվը կոչվում է գրաֆի [[քրոմատիկ թիվ]]: Դրա որոշումը NP-լրիվ խնդիր է<ref>[[քրոմատիկ թիվ|Քրոմատիկ թվի]] մասին [http://mathworld.wolfram.com/ChromaticNumber.html Wolfram MathWorld-ում]</ref>, սակայն հայտնի են բազմաթիվ գնահատականներ: Օրինակ, ըստ [[Բրուքսի թեորեմ]]ի <ref>[[Բրուքսի թեորեմ]]ը [http://mathworld.wolfram.com/BrooksTheorem.html Wolfram MathWorld-ում]</ref>, գրաֆի քրոմատիկ թիվը չի գերազանցում գրաֆի առավելագույն աստիճանը, բացառությամբ [[ցիկլ (գրաֆների տեսություն)|ցիկլերի]] և լրիվ գրաֆների:
 
[[File:World using the four color theorem.png|thumb|Աշխարհի քարտեզը ներկված չորս գույներով․ հարևան երկրները տարբեր գույներով են: [[Չորս գույների թեորեմ]]ի համաձայն, ցանկացած քարտեզ ունի այսպիսի ներկում]]
 
==== Կողային ներկումներ ====
Երբ գագաթների փոխարեն ներկվում են կողերը և պահանջ է դրվում, որ կից կողերը ունենան տարբեր գույներ, այդպիսի ներկումը կոչվում է ''ճիշտ կողային ներկում'': Ճիշտ կողային ներկման դեպքում նվազագույն գույների քանակը կոչվում է գրաֆի [[քրոմատիկ դաս]], որը հաշվելը ևս NP-լրիվ խնդիր է: [[Վիզինգի թեորեմ]]ի համաձայն, քրոմատիկ դասը կարող է հավասար լինել գրաֆի առավելագույն աստիճանին, կամ դրանից մեծ լինել ճիշտ մեկով:
 
Գրաֆի ճիշտ կողային ներկումը համարժեք է գրաֆի [[կողային գրաֆ]]ի ճիշտ գագաթային ներկմանը:
 
{{ՎՊԵ|Graph theory}}
 
[[Կատեգորիա:Գրաֆների տեսություն| ]]
[[Կատեգորիա:Ինֆորմատիկա]]
 
{{link FA|nl}}
144 973

edits