--------------------------------------------------------------------------
Fie un graf neorientat complet cu 30 de noduri. Indicați numărul de muchii ce pot fi eliminate, astfel încât graful parțial obținut să fie conex și fără cicluri. 
--------------------------------------------------------------------------
Teorie:
Două vârfuri între care există muchie se numesc adiacente.
Un graf parțial se obține dintr-un graf prin păstrarea tuturor vârfurilor și prin suprimarea unor muchii.
Numărul grafurilor parțiale este 2^m.
Se numește lanț o succesiune de vârfuri L=[x1,x2,⋯xk] cu proprietatea că oricare două vârfuri consecutive sunt adiacente.
Fie G=(X, U) un graf neorientat. Graful G se numește graf complet dacă oricare două vârfuri distincte ale sale sunt adiacente. Un graf complet cu n vârfuri se notează Kn.
Într-un graf complet cu n vârfuri sunt C(2,n)=n∗(n−1)/2 muchii și fiecare vârf are gradul n-1.
Sunt 2^(n∗(n−1)/2) grafuri neorientate distincte cu n vârfuri.
Un graf se numește graf conex dacă între oricare două noduri există cel puțin un lanț.
Se numește CICLU un lanț simplu în care primul vârf este identic cu ultimul.
--------------------------------------------------------------------------
n=30
În graful dat avem m=n*(n-1)/2=30*29/2=15*29=435 de muchii.
Nodurile ar putea fi dispuse în cerc, într-un "n"-gon, asta înseamnă că am avea nevoie de n-1 muchii=29 de muchii ca să rămână conex și fără cicluri.
Concluzia, ar trebui să eliminăm: 435-x=29 => x=435-29 => x=406 muchii
--------------------------------------------------------------------------
a) 30
b) 406
c) 435
d) 436 (*)
--------------------------------------------------------------------------
Răspuns corect: b)

