Պատմիր ոչ ուղղորդված գրաֆի և նրա հատկությունների մասին։

Անուղղակի գրաֆը զույգ է $(V, E)$, որտեղ $V$-ն հանգույցների (կետերի) հավաքածուն է, իսկ $E$-ն եզրերի հավաքածուն է: Յուրաքանչյուր եզր ներկայացնում է ոչ կարգավորված զույգ ${u, v}$ հանգույցներից, որտեղ $u, v \in V$:

Հիմնական հատկություններ՝

• Եզրեր առանց ուղղության: Հետագիծը հանգույցների միջև սիմետրիկ է: Եթե կա եզր $u$ և $v$ միջև, դա նշանակում է, որ կարելի է շարժվել ինչպես $u$-ից $v$-ին, այնպես էլ $v$-ից $u$-ին:
• Հանգույցի աստիճան: Այդ հանգույցին հարող եզրերի թիվը: Նշվում է որպես $deg(v)$:
• Բոլոր հանգույցների աստիճանների գումարը: Յուրաքանչյուր անուղղակի գրաֆում, բոլոր հանգույցների աստիճանների գումարը հավասար է եզրերի թվի կրկնապատկմանը: $\sum_{v \in V} deg(v) = 2|E|$:
• Միջանցք: Հանգույցների հաջորդականություն $v_0, v_1, ..., v_k$, որտեղ յուրաքանչյուր զույգ $(v_i, v_{i+1})$ եզր է:
• Շրջան: Միջանցք, որը սկսվում և ավարտվում է նույն հանգույցում, և մնացած բոլոր հանգույցները եզակի են:
• Կապվածություն: Գրաֆը կոչվում է կապակցված, եթե ցանկացած երկու հանգույցների միջև կա միջանցք: Անկապ գրաֆը բաղկացած է մի քանի կապակցված բաղադրիչներից:
• Բարձված գրաֆ: Յուրաքանչյուր եզրին կարող է նշանակվել որոշ թվային արժեք (բարձունք):
• Չլինել շղթաներ և բազմակի եզրեր (պարզ գրաֆ): Պարզ անուղղակի գրաֆներում, երկու հանգույցների միջև կարող է լինել ոչ ավել, քան մեկ եզր, և եզրերը չեն կապում հանգույցը ինքն իր հետ (չկա շղթա):
• Ավելի լրիվ գրաֆ: Գրաֆ, որի մեջ յուրաքանչյուր տարբեր հանգույցների զույգը կապված է եզրով: Նշվում է $K_n$, որտեղ $n$ - հանգույցների թիվը:
• Երկկողմանի գրաֆ: Հանգույցների հավաքածուն բաժանվում է երկու անփոփոխ ենթախումբերի $U$ և $W$, այնպես, որ յուրաքանչյուր եզր կապում է $U$-ի հանգույցը $W$-ի հանգույցի հետ։