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

փաստերի ավելացում, ենթագրաֆների և մինորների խնդիրներ
(փաստերի ավելացում, պատկերում)
(փաստերի ավելացում, ենթագրաֆների և մինորների խնդիրներ)
 
Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են [[''հարթ'' գրաֆներ|հարթ գրաֆներ]]: Եթե այդպիսի պատկերում հնարավոր չէ, ապա հատումների նվազագույն քանակը, որին կարելի է հասնել, կոչվում է գրաֆի [[խաչումների թիվ]]: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի: Հարթ գրաֆների հետազոտությունը, ինչպես նաև տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են:
 
==Գրաֆների տեսության խնդիրներ==
===Ենթագրաֆներ, մինորներ===
Գրաֆների տեսության հետաքրքիր խնդիրներից է '''ենթագրաֆների իզոմորֆիզմի խնդիրը''', երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի [[ենթագրաֆ]]ի գոյությունը: Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) '''ժառանգական''' են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը: Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է: Մասնավորապես, տրված գրաֆում ամենամեծ [[լրիվ|լրիվ գրաֆ]] ենթագրաֆի գտնելը [[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}}