Grafuri neorientate

Grafuri — grafuri neorientate, reprezentări, conexitate, arbori

Determinarea gradelor, a numărului de muchii și a componentelor conexe dintr-o matrice de adiacență sau dintr-o listă de muchii.
Deosebirea dintre graf parțial, subgraf, graf complet și arbore, cu verificarea proprietăților care le definesc.
Aplicarea formulelor de numărare a muchiilor, a gradelor și a grafurilor parțiale la cerințe de tip Subiectul I.

Într-un graf neorientat muchia este o pereche neordonată de vârfuri distincte, iar matricea de adiacență este simetrică, cu diagonala principală nulă.
Suma gradelor tuturor vârfurilor este 2 * m, deci este întotdeauna pară.
Un lanț este elementar dacă nu repetă vârfuri; un ciclu se închide în vârful de pornire, are cel puțin trei muchii și nu repetă muchii.
Graful este conex dacă între oricare două vârfuri există un lanț; altfel se descompune în componente conexe, iar un vârf izolat formează singur o componentă.
Graful complet Kn are n * (n - 1) / 2 muchii, iar fiecare vârf are gradul n - 1.
Graful parțial pierde numai muchii, iar un graf cu m muchii are 2^m grafuri parțiale; subgraful pierde vârfuri împreună cu muchiile lor.
Un arbore este conex și fără cicluri, are exact n - 1 muchii, iar n - 1 muchii singure nu sunt suficiente pentru a garanta un arbore.
Cu n vârfuri și p componente conexe, numărul de muchii este între n - p și (n - p) * (n - p + 1) / 2.