«Գրաֆների տեսություն»–ի խմբագրումների տարբերություն
Content deleted Content added
փաստերի ավելացում, ենթագրաֆների և մինորների խնդիրներ |
փաստերի ավելացում, ներկումներ, լուսանկար |
||
Տող 4.
Գրաֆների տեսության հիմնական հասկացությունների համար այցելեք [[Գրաֆների տեսության բառարան]]։
{| align="center"
Տող 22 ⟶ 21՝
==Սահմանումներ==
[[File:Multi-pseudograph.svg|thumb|Սա չկողմնորոշված պսևդոգրաֆ է, քանի որ պարունակում է ինչպես պատիկ կողեր (կարմիր), այնպես էլ օղակներ (կապույտ)]]
'''Գրաֆը''' սահմանվում է որպես կարգավոր զույգ G=(V,E), որտեղ V-ն '''գագաթների''' (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ '''կողերի''' (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են ''չկողմնորոշված'' և ''հասարակ'' գրաֆներ:
Կողին պատկանող գագաթները կոչվում են այդ գագաթի ''ծայրակետեր'': Հաճախ ''{u, v}'' կողը կրճատ նշանակում են ''uv''-ով:
Երբեմն E բազմությունը սահմանվում է որպես (իրարից տարբեր) գագաթների չկարգավորված զույգերի մուլտիբազմություն: Այսպես սահմանվող օբյեկտները կոչվում են '''մուլտիգրաֆներ''': Գագաթների միևնույն զույգի միջև մեկից ավելի կողերը կոչվում են '''պատիկ''' կողեր: Եթե թույլատրվում են նաև այնպիսի կողեր, որոնց երկու ծայրերն էլ միանում են միևնույն գագաթին (առաջացնելով ''օղակ''), այդ դեպքում ասում են, որ գործ ունենք '''պսևդոգրաֆի''' հետ:
Սովորաբար V և E բազմությունները ընդունվում են վերջավոր: Հակառակ դեպքում գործ ունենք '''անվերջ գրաֆների''' հետ, որոնց համար վերջավոր գրաֆների բազմաթիվ հատկություններ տեղի չունեն: Գրաֆի '''կարգը''' գագաթների բազմության հզորությունն է: Որևէ գագաթի '''աստիճանը''' այդ գագաթին միացած կողերի քանակն է: Պսևդոգրաֆների դեպքում, երբ որևէ կողի երկու ծայրերն էլ միացած են միևնույն գագաթին, այդպիսի կողերը (օղակները) հաշվվում են երկու անգամ:
==Կիրառություններ==
[[File:Wikipedia multilingual network graph July 2013.svg|thumb|Գագաթները [[Վիքիպեդիա]]յի լեզվական տարբերակներն են: Կողերով միացված են այն տարբերակները, որոնցում խմբագրումներ կատարել է միևնույն մասնակիցը 2013-ի ամռանը կատարված հետազոտության ժամանակ <ref>{{Cite arXiv|eprint=1312.0976|last1=Hale|first1=Scott A.|title=Multilinguals and Wikipedia Editing|class=cs.CY|year=2013}}</ref>]]
Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ: Այս և այլ ուղղություններում բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային [[ալգորիթմ]]ներով:
Համակարգչային գիտություններում գրաֆներով մոդելավորում են համակարգչային ցանցերը, տվյալների կառուցվածքները, հաշվարկի ընթացքը և այլն: Օրինակ, որպես գագաթների բազմություն կարելի է ընտրել ինտերնետային կայքերը, իսկ կայքերի միջև հղումները կդառնան ուղղորդված կողեր գագաթների միջև: Գրաֆների միջոցով ներկայացվող տվյալները արդյունավետ պահելու և կառավարելու համար գոյություն ունեն գրաֆային [[տվյալների հենք]]եր: Գրաֆների տեսությամբ են մոդելավորվում գերմեծ ինտեգրալ սխեմաների նախագծման ժամանակ առաջացող բազմաթիվ խնդիրներ (օրինակ՝ routing-ի խնդիրը):
Քիմիայում և պինդ մարմնի ֆիզիկայում գրաֆների միջոցով մոդելավորում են ատոմները և նրանց միջև կապերը:
==Գրաֆների պատկերում==
[[File:Social Network Analysis Visualization.png|thumb|Մեծ սոցիալական գրաֆի պատկերում ուժային ալգորիթմով]]
Գրաֆները հաճախ ներկայացվում են հարթության վրա պատկերի միջոցով: Յուրաքանչյուր գագաթի համար պատկերվում է կետ կամ շրջան, իսկ կողերը ներկայացվում են գագաթները միացնող կորերով: Ուղղորդված գրաֆների դեպքում կորերի մի ծայրում պատկերվում են սլաքներ:
Տող 46 ⟶ 50՝
==Գրաֆների տեսության խնդիրներ==
===Ենթագրաֆներ, մինորներ===
[[File:Petersen Wagner minors.svg|thumb|360px| [[Պետերսենի գրաֆ]]ը հարթ չէ: Այն պարունակում է ինչպես ''K''<sub>5</sub> մինոր (ձախից), այնպես էլ ''K''<sub>3,3</sub> մինոր (աջից): Պետերսենի գրաֆը պատկերված է փոքր գագաթներով և սև կողերով: Դեղին գույնով նշված են մինորները:]]
Գրաֆների տեսության հետաքրքիր խնդիրներից է '''ենթագրաֆների իզոմորֆիզմի խնդիրը''', երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի [[ենթագրաֆ]]ի գոյությունը: Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) '''ժառանգական''' են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը: Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է: Մասնավորապես, տրված գրաֆում ամենամեծ [[լրիվ|լրիվ գրաֆ]] ենթագրաֆի գտնելը [[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> լրիվ գրաֆը որպես մինոր:
=== Գրաֆների ներկումներ ===
[[Image:Petersen graph 3-coloring.svg|thumb|right|[[Պետերսենի գրաֆ]]ի ճիշտ գագաթային ներկում 3 գույներով: Ավելի քիչ գույներով ճիշտ ներկում կառուցել հնարավոր չէ]]
Գրաֆների տեսության բազմաթիվ խնդիրներում գրաֆի տարբեր տարրերին (կող, գագաթ և այլն) համապատասխանեցվում են ''գույներ'' կամ թվեր: Այդպիսի արտապատկերումները գրաֆի տարրերից թվերին կոչվում են [[գրաֆների ներկումներ|'''ներկումներ''']]:
==== Գագաթային ներկումներ ====
''Ճիշտ գագաթային ներկման'' դեպքում գագաթներին համապատասխանեցվում են գույներ (թվեր) այնպես, որ հարևան գագաթների գույները լինեն տարբեր: Ակնհայտորեն, բոլոր գրաֆները ունեն այդպիսի ներկումներ, քանի որ կարելի է ամեն գագաթին համապատասխանեցնել մի նոր գույն: Սակայն խնդիր է առաջանում գտնել գույների ամենափոքր թիվը, որոնցով կարելի է ապահովել ճիշտ գագաթային ներկում: Այդ թիվը կոչվում է գրաֆի [[քրոմատիկ թիվ]]: Դրա որոշումը 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|Աշխարհի քարտեզը ներկված չորս գույներով․ հարևան երկրները տարբեր գույներով են: [[Չորս գույների թեորեմ]]ի համաձայն, ցանկացած քարտեզ ունի այսպիսի ներկում]]
Հարթ գրաֆների դեպքում քրոմատիկ թիվը գտնելու խնդիրը հայտնի է որպես քարտեզ ներկելու խնդիր: Եթե երկրներին (կամ ցանկացած տարածքային միավորին) համպատախասնեցվեն գագաթներ հարթության վրա, իսկ հարևան երկրները միացվեն կողերով, ապա ճիշտ գագաթների ներկումը կհամապատասխանի քարտեզի ներկմանը: [[Չորս գույների թեորեմ]]ի համաձայն, հարթ գրաֆի քրոմատիկ թիվը չորսից մեծ չէ, հետևաբար ցանկացած քարտեզ ներկելու համար բավարար է օգտագործել չորս գույն:
Ճիշտ գագաթային ներկումների հայտնի չլուծված խնդիրներից է [[Հադվիգերի հիպոթեզ]]ը, ըստ որի ''k'' քրոմատիկ թիվ ունեցող գրաֆը պետք է պարունակի ''k''-գագաթանի լրիվ գրաֆը որպես մինոր: Այս հիպոթեզը չորս գույների թեորեմի ընդհանրացումն է:
==== Կողային ներկումներ ====
Երբ գագաթների փոխարեն ներկվում են կողերը և պահանջ է դրվում, որ կից կողերը ունենան տարբեր գույներ, այդպիսի ներկումը կոչվում է ''ճիշտ կողային ներկում'': Ճիշտ կողային ներկման դեպքում նվազագույն գույների քանակը կոչվում է գրաֆի [[քրոմատիկ դաս]], որը հաշվելը ևս NP-լրիվ խնդիր է: [[Վիզինգի թեորեմ]]ի համաձայն, քրոմատիկ դասը կարող է հավասար լինել գրաֆի առավելագույն աստիճանին, կամ դրանից մեծ լինել ճիշտ մեկով:
Գրաֆի ճիշտ կողային ներկումը համարժեք է գրաֆի [[կողային գրաֆ]]ի ճիշտ գագաթային ներկմանը:
Ինչպես գագաթային, այնպես էլ կողային ներկումների համար սահմանվում են '''ցուցակային ներկումներ''', երբ յուրաքանչյուր գագաթի (կողի) համապատասխանեցվում է գույների ցուցակ, որտեղից անհրաժեշտ է ընտրել գույներ այնպես, որ ստացված ներկումը լինի ճիշտ: [[Կողային ցուցակային ներկման հիպոթեզ]]ի համաձայն, ցանկացած օղակ չպարունակող մուլտիգրաֆի համար կողային ցուցակային քրոմատիկ թիվը պետք է հավասար լինի գրաֆի քրոմատիկ դասին: Այս խնդիրը ևս լուծված չէ <ref>[[Կողային ցուցակային ներկման հիպոթեզ]]ը [http://www.openproblemgarden.org/?q=node/2110 Open Problem Garden-ում]</ref>:
==== Տոտալ ներկումներ ====
Ներկումը կոչվում է ''տոտալ'', երբ ներկվում են ինչպես գագաթները, այնպես էլ կողերը: Այս ոլորտի ամենահայտնի խնդիրը [[տոտալ ներկման հիպոթեզ]]ն է, որը ձևակերպվել է Վիզինգի և Բեհզադի կողմից 1965թ․ և մինչ այժմ լուծված չէ <ref>[[Տոտալ ներկման հիպոթեզ]]ը [http://www.openproblemgarden.org/op/behzads_conjecture Open Problem Garden-ում]</ref>:
== Ծանոթագրություններ ==
{{ծանցանկ}}
{{ՎՊԵ|Graph theory}}
| |||