Pastāsti par neorientētu grafu un tā īpašībām.

Neorientēts grafs ir pāris $(V, E)$, kur $V$ ir virsotņu (mezglu) kopums, bet $E$ ir malu kopums. Katra mala ir neorientēta pāris ${u, v}$ virsotnēm $u, v \in V$.

Galvenās īpašības:

• Neorientētas malas: Savienojums starp virsotnēm ir simetrisks. Ja starp $u$ un $v$ ir mala, tas nozīmē, ka var pārvietoties gan no $u$ uz $v$, gan no $v$ uz $u$.
• Virsotnes pakāpe: Malu skaits, kas ir incidentā ar šo virsotni. To apzīmē kā $deg(v)$.
• Virsotņu pakāpju summa: Jebkurā neorientētā grafikā virsotņu pakāpju summa ir divkāršā malu skaita. $\sum_{v \in V} deg(v) = 2|E|$.
• Ceļš: Virsotņu secība $v_0, v_1, ..., v_k$, kur katra pāris $(v_i, v_{i+1})$ ir mala.
• Cikls: Ceļš, kas sākas un beidzas tajā pašā virsotnē, bet visas pārējās virsotnes ir unikālas.
• Saites: Grafs ir saistīts, ja pastāv ceļš starp jebkuru virsotņu pāri. Nesaites grafs sastāv no vairākām saistītām komponentēm.
• Svars: Katram malai var piešķirt skaitlisku vērtību (svaru).
• Bez līnijas un daudzlīnijām (vienkāršs grafiks): Vienkāršos neorientētajos grafikos starp divām virsotnēm var būt ne vairāk kā viena mala, un malas nesavieno virsotni ar sevi (bez līnijas).
• Pilns grafiks: Grafiks, kurā katra dažādo virsotņu pāra ir savienots ar malu. To apzīmē kā $K_n$, kur $n$ ir virsotņu skaits.
• Divdēļu grafiks: Virsotņu kopums var tikt sadalīts divās nesaskaras apakškopās $U$ un $W$, tā, ka katra mala savieno virsotni no $U$ ar virsotni no $W$.