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

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

Համակարգչային գիտություններում գրաֆներով մոդելավորում են համակարգչային ցանցերը, տվյալների կառուցվածքները, հաշվարկի ընթացքը և այլն։ Օրինակ, որպես գագաթների բազմություն կարելի է ընտրել ինտերնետային կայքերը, իսկ կայքերի միջև հղումները կդառնան ուղղորդված կողեր գագաթների միջև։ Գրաֆների միջոցով ներկայացվող տվյալները արդյունավետ պահելու և կառավարելու համար գոյություն ունեն գրաֆային [[տվյալների հենք]]եր։ Գրաֆների տեսությամբ են մոդելավորվում գերմեծ ինտեգրալ սխեմաների նախագծման ժամանակ առաջացող բազմաթիվ խնդիրներ (օրինակ՝ routing-ի խնդիրը):։

Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են [[''հարթ'' գրաֆներ|հարթ գրաֆներ]]: Ընդհանուր դեպքում, կողերի հատումների նվազագույն քանակը, որին կարելի է հասնել գրաֆը հարթության վրա պատկերելիս, կոչվում է գրաֆի [[խաչումների թիվ]] <ref>[[Խաչումների թիվ|Խաչումների թվի]] մասին [http://mathworld.wolfram.com/GraphCrossingNumber.html Wolfram MathWorld-ում]</ref>: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի։ Հարթ գրաֆների հետազոտությունը, ինչպես տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են։ Գրաֆների պատկերման խնդիրները այլ մակերևույթների վրա (օրինակ՝ տոռերի) ուսումնասիրում է ''տոպոլոգիական գրաֆների տեսությունը'':

Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը։ H գրաֆը կոչվում է G գրաֆի [[մինոր (գրաֆների տեսություն)|'''մինոր''']], եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր [[կծկելով]]: Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է։ [[Վագների թեորեմ]]ը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում <math>K_{3,3}</math> [[լրիվ երկկողմանի գրաֆ]]ը և <math>K_5</math> լրիվ գրաֆը որպես մինոր։