----------------------------------------------------------
Se consideră un graf neorientat complet, cu 40 de vârfuri. Care este numărul maxim de muchii care pot fi eliminate, astfel încât graful să fie eulerian și hamiltonian?
----------------------------------------------------------
Teorie:
Un graf neorientat 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.

Se numește LANȚ o succesiune de vârfuri L=[x1,x2,⋯xk] cu proprietatea că oricare două vârfuri consecutive sunt adiacente. Vârfurile x1 şi xk se numesc extremitățile lanțului. Numărul k-1 se numește lungimea lanțului și este numărul de muchii din care este format.
Lanțul care conține numai vârfuri distincte, două câte două, este LANȚ ELEMENTAR.
Lanțul care conține numai muchii distincte este LANȚ SIMPLU.
Dacă muchiile unui lanț nu sunt distincte se numește LANȚ COMPUS.

Se numește CICLU un lanț simplu în care primul vârf este identic cu ultimul. Dacă toate vârfurile sunt distincte, mai puțin primul și ultimul, se numește CICLU ELEMENTAR.
Lungimea unui ciclu este egală cu numărul de muchii din ciclu. Lungimea minimă a unui ciclu este 3.

Se numește GRAF HAMILTONIAN un graf care conține un CICLU HAMILTONIAN. Se numește CICLU HAMILTONIAN un ciclu elementar care conține toate vârfurile grafului.
Un G un graf neorientat. Dacă are n≥3 vârfuri şi gradul oricărui vârf verifică inegalitatea d(x)≥n/2 atunci G este HAMILTONIAN.

Se numește GRAF EULERIAN un graf care conține un CICLU EULERIAN. Se numește CICLU EULERIAN un ciclu care conține toate muchiile grafului.
----------------------------------------------------------
n=40
Graf complet: Kn: C(2,n)=n∗(n−1)/2: 40*39/2=20*39=780 muchii
Trebuie să radiem un număr maxim de muchii pentru ca graful să rămână eulerian și hamiltonian, în același timp.
Ca să rămână hamiltonian trebuie să mai rămână suficiente muchii cât să putem creea un ciclu hamiltonian (să pot uni cu un ciclu elementar toate vârfurile). Dacă ar fi de 3 vârfuri, e de ajuns să avem 3 muchii => la 40 de muchii e de ajuns să avem 40 de muchii (un "cerc" care să cuprindă toate vârfurile). În acest sens, îndeplinește și condiția de graf eulerian, pentru că există un ciclu eulerian (un ciclu care să conțină toate muchiile grafului).
Prin urmare, din cele 780 câte trebuie să radiez/șterg pentru a ajunge la 40?!
Răspuns: 780-40 = 740 muchii maximale pot radia.
----------------------------------------------------------
a) 40
b) 760
c) 740 (*)
d) 780
----------------------------------------------------------
Răspuns corect: c)

