«Գրաֆների տեսություն»–ի խմբագրումների տարբերություն
Content deleted Content added
չ լուսանկար |
փաստերի ավելացում, պատկերում |
||
Տող 36.
Քիմիայում և պինդ մարմնի ֆիզիկայում գրաֆների միջոցով մոդելավորում են ատոմները և նրանց միջև կապերը:
==Գրաֆների պատկերում==
Գրաֆները հաճախ ներկայացվում են հարթության վրա պատկերի միջոցով: Յուրաքանչյուր գագաթի համար պատկերվում է կետ կամ շրջան, իսկ կողերը ներկայացվում են գագաթները միացնող կորերով: Ուղղորդված գրաֆների դեպքում կորերի մի ծայրում պատկերվում են սլաքներ:
Ակնհայտորեն, միևնույն գրաֆը կարելի է պատկերել տարբեր ձևերով, և ընդհանուր դեպքում դժվար է ճանաչել, թե երբ են տարբեր պատկերները համապատասխանում միևնույն գրաֆին: Գրաֆների գեղեցիկ կամ հարմար պատկերումը գրաֆների տեսության բարդագույն խնդիրներից է: Մշակված են մի շարք որակի չափանիշներ (կողերի հատումների թիվը, համաչափությունը, գագաթների հեռավորությունը իրենցով չանցնող կողերից և այլն), ինչպես նաև բազմաթիվ պատկերման ալգորիթմներ <ref>[http://www.graphdrawing.org/ Գրաֆների պատկերում (անգլերեն)]</ref>:
Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են [[''հարթ'' գրաֆներ|հարթ գրաֆներ]]: Եթե այդպիսի պատկերում հնարավոր չէ, ապա հատումների նվազագույն քանակը, որին կարելի է հասնել, կոչվում է գրաֆի [[խաչումների թիվ]]: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի: Հարթ գրաֆների հետազոտությունը, ինչպես նաև տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են:
{{ՎՊԵ|Graph theory}}
| |||